力扣每日一题：两数相加

简介：

题目描述


我的解题过程

思路

1. 首先创建两个指针p、q指向两个链表的首部，由于是逆序的，所两个指针的数据可以直接相加
2. 将得到的结果放入一个新链表中，有进位就进行标志，p、q同时向后移动，下一次两个指针指向的数据相加时需要考虑前面的进位，再计算下一次是否需要进位
3. 考虑p、q长度不一的情况

这样做下来也没什么毛病，顺利通过了官网的检验，但是官方的代码只有19行，我的代码去掉注释达到了70行，别人用一个中间变量就很好的规避了不用分两个链表长度不同的情况

不得不说官方的代码质量很高啊，我还是太年轻，需要继续学习

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p = l1;
        ListNode q = l2;
        ListNode l3 = new ListNode();
        ListNode r = l3;

        //定义一个表示是否有进位的布尔值
        boolean flag = false;

        while (p != null && q != null){
            //有进位就要将结果加一
            int res = p.val + q.val;
            if (flag){
                res = p.val + q.val + 1;
                flag = false;
            }
            //如果结果大于10表明下一次计算需要进位
            if (res >= 10){
                res = res - 10;
                flag = true;
            }
            r.val = res;
            //所有同时往后移动
            p = p.next;
            q = q.next;
            //这个判断一定要加，不然直接默认r.val为0
            if(p != null && q != null){
                r.next = new ListNode();
                r = r.next;
            }
        }
        //最后肯定有一个是空的，把非空的链表依次赋值给l3
        if (p != null || q != null){
            //将r再往后移动一格
            r.next = new ListNode();
            r = r.next;
            while (p != null){
                int res=p.val;
                //有进位就要将结果加一
                if (flag){
                    res = p.val + 1;
                    flag = false;
                }
                //如果结果大于10表明下一次计算需要进位
                if (res >= 10){
                    res = res - 10;
                    flag = true;
                }
                r.val = res;
                //所有同时往后移动
                p = p.next;
                if(p != null){
                    r.next = new ListNode();
                    r = r.next;
                }
            }
            while (q != null){
                //有进位就要将结果加一
                int res=q.val;
                if (flag){
                    res = q.val + 1;
                    flag = false;
                }
                //如果结果大于10表明下一次计算需要进位
                if (res >= 10){
                    res = res - 10;
                    flag = true;
                }
                r.val = res;
                //所有同时往后移动
                q = q.next;
                if(q != null){
                    r.next = new ListNode();
                    r = r.next;
                }
            }
        }
        //如果还有进位，直接继续赋值1
        if(flag){
            r.next = new ListNode();
            r = r.next;
            r.val = 1;
        }
        return l3;
    
    }
}

代码复杂度分析

时间复杂度：代码进行了两次for循环，因此时间复杂度是O(n²)

空间复杂度：开辟了两个单元的数组res保存结果，空间复杂度为O(1)

官方解题过程

思路

1. 先用for循环遍历数组，将nums[i]作为第一个数值
2. 如果再去遍历一次数组来找另一个值效率太低，选择引用查找效率极高的哈希表来找第二个值

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
          	//注意i不能重复，所以&&后面的代码要加上
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

代码复杂度分析

时间复杂度：引入了查找速度为O(1)哈希表，查找效率大大提升，只用了一层for循环，时间复杂度为O(n)

空间复杂度：因为引入了哈希表，因此空间复杂度变为O(n)，以空间换时间

总结

1. 暴力求解法，代码执行时间为70ms左右，引入哈希表时间为3ms左右
2. 所以涉及到查找的算法，如果在空间充足的情况下，可以引用哈希表来大大优化时间
3. 上面是官方给出的第二种解法，这种解法不能解决数组中有重复值得情况，如果有重复值就需要第三种解法了