力扣记录：Hot100（1）——1-19

1 两数之和

• 之前做过，使用HashMap存储数组中的数及其下标，遍历查找哈希表中是否存在目标值减当前值，注意两数下标应不同。
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
   
    public int[] twoSum(int[] nums, int target) {
   
        //使用HashMap存储数及下标
        Map<Integer, Integer> map = new HashMap<>();
        //遍历查找哈希表中是否存在目标值减当前值
        for(int i = 0; i < nums.length; i++){
   
            if(map.containsKey(target - nums[i])){
   
                return new int[]{
   i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        //没找到
        return new int[2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2 两数相加

• 分别遍历两个链表得到长度，在较长的链表上直接进行修改，设置虚拟头节点最后返回，设置进位符号并在每次相加后对进位进行判断，设置前一个节点用于最后一位进位时新建节点。
  • 优化：可以不用分别遍历两个链表，直接选择一条链表进行修改，不够长则直接新建节点。
  • 时间复杂度O(m + n)（优化后为O(max(m, n)），空间复杂度O(1)

class Solution {
   
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
   
        //直接在l1上修改
        //先判断两个链表的长度
        int leng1 = 0;
        ListNode temp1 = l1;
        while(temp1 != null){
   
            leng1 += 1;
            temp1 = temp1.next;
        }
        int leng2 = 0;
        ListNode temp2 = l2;
        while(temp2 != null){
   
            leng2 += 1;
            temp2 = temp2.next;
        }
        //将l1设为较长的链表
        if(leng1 < leng2){
   
            ListNode temp = l1;
            l1 = l2;
            l2 = temp;
        }
        ListNode head = new ListNode(0, l1); //虚拟头节点
        ListNode pre = null;    //最后一位进位需要新建节点
        int c = 0;  //进位
        while(l1 != null){
   
            //相加
            if(l2 != null){
   
                l1.val += l2.val + c;
            }else{
   
                l1.val += c;
            }
            //判断是否进位
            if(l1.val > 9){
   
                c = 1;
                l1.val %= 10;
            }else{
   
                c = 0;
            }
            //下一节点
            pre = l1;
            l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        //最后一位进位
        if(c == 1){
   
            pre.next = new ListNode(1);
        }
        return head.next;
    }
    //优化
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
   
        //直接在l1上修改
        ListNode head = new ListNode(0, l1); //虚拟头节点
        ListNode pre = null;    //最后一位进位需要新建节点
        int c = 0;  //进位
        while(l1 != null || l2 != null){
   
            //相加，若节点为null则加数为0，否则为节点值
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + c;
            c = sum / 10;   //判断是否进位
            if(l1 == null){
   
                pre.next = new ListNode(sum % 10, null);
            }else{
   
                l1.val = sum % 10;
            }
            //下一节点
            pre = l1 == null ? pre.next : l1;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        //最后一位进位
        if(c == 1){
   
            pre.next = new ListNode(1);
        }
        return head.<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92