algorithm

两数之和三数之和四数之和

宋正兵 on 2021-04-19

最近刷题遇到了好几次这个类型的题，于是在此做个总结。

两数之和

两数之和

利用 Map 来进行记录和快速查找

题目大意：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

思路：我们只讨论最优解，一次遍历就能够找到这两个数。我们利用 Map 来存放已经遍历过的数字和其对应的下标。对于当前遍历到的第 i 个数字，如果我们能够在 Map 的中找到 key 为 target-nums[i] 的数据，说明找到了那两个整数，返回它们的下标即可。

时间复杂度：$O(N)$，其中 $N$ 是数组中元素的个数。对于每一个元素 x，我们可以 $O(1)$ 地寻找 target-x。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[] {hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

三数之和

先对数组进行排序，固定其中一个指针指向数字 base，再用双指针在 base 之后的区域内寻找合适的位置

三数之和

题目大意：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0且不重复的三元组。

思路：

  1. 对数组进行排序
  2. 遍历排序后的数组：
    1. 若 nums[i] > 0：因为是排序后的数组，所以不可能有三个数之和等于0，直接返回结果；
    2. 若 nums[i] == nums[i - 1]：跳过，避免出现重复解；
    3. 令左指针 l = i + 1，右指针 r = nums.length - 1，当 l < r 时执行循环：
      • 当 nums[i] + nums[l] + nums[r] == 0，执行循环，跳过左边界和右边界上重复的元素，避免重复解，同时将 l 和 r 移动到下一位置，寻找新的解；
      • 若 nums[i] + nums[l] + nums[r] > 0，说明 nums[r] 太大，右边界 r 左移；
      • 若 nums[i] + nums[l] + nums[r]< 0，说明 nums[l] 太小，左边界 l 右移；

时间复杂度：$O(N^{2})$，其中 $N$ 是数组的长度。数组排序 $O(NlogN)$，遍历数组 $O(N)$，双指针遍历 $O(N)$，总体时间复杂度为 $O(NlogN) + O(N)*O(N)$。

代码：

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resList = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 3) {
            return resList;
        }
        Arrays.sort(nums);
        // 根据每个nums[i]去找另外的两个数字
        for (int i = 0; i < nums.length; i++) {
            // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if (nums[i] > 0) {
                break;
            }
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // nums[i] + nums[l] + nums[r] == 0
            int l = i + 1, r = nums.length - 1; 
            while (l < r) {
                int temp = nums[i] + nums[l] + nums[r];
                if (temp == 0) {
                    resList.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    // 去重，以nums[i]开头的三元组中不再包含当前值
                    while(l < r && nums[l + 1] == nums[l]) {
                        l++;
                    }
                    while(l < r && nums[r - 1] == nums[r]) {
                        r--;
                    }
                    l++;
                    r--;
                } else if (temp < 0) {
                    // 说明nums[l]太小，需要找一个更大的元素
                    l++;
                } else {
                    // 说明nums[n]太大，需要找一个更小的元素
                    r--;
                }
            }
        }
        return resList;
    }
}

四数之和

和三数之和类似，只不过是固定了前两个指针，然后利用双指针移动来寻找满足条件的解。

四数之和

题目大意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target相等？找出所有满足条件且不重复的四元组。

思路：

  1. 对数组进行排序
  2. 两层 for 遍历排序后的数组：
    1. 若 nums[i] + nums[j] + nums[nums.length - 2] + nums[nums.length - 1] < target，当前组合所能产生的最大值小于 target，跳过；
    2. 若 nums[i] == nums[i - 1] 或者 nums[j] == nums[j - 1]，跳过，避免出现重复解；
    3. 令左指针 l = j + 1，右指针 r = nums.length - 1，当 l < r 时执行循环：
      • 若 nums[i] + nums[j] + nums[l] + nums[r] == target，执行循环，跳过左边界和右边界上重复的元素，避免重复解，同时将 l 和 r 移动到下一位置，寻找新的解；
      • 若 nums[i] + nums[j] + nums[l] + nums[r] > target，说明 nums[r] 太大，右边界 r 左移；
      • 若 nums[i] + nums[j] + nums[l] + nums[r] < target，说明 nums[l] 太小，左边界 l 右移；

时间复杂度：$O(N^{3})$，其中 $N$ 是数组的长度。排序的时间复杂度是 $O(NlogN)$，枚举四元组的时间复杂度是 $O(N^{3})$，因此总时间复杂度是 $O(NlogN + N^{3})$

代码：

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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums == null || nums.length  < 4) {
            return list;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; i++) {
            // 剪枝，去除重复
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                // 剪枝，去除重复
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int l = j + 1, r = nums.length - 1;
                while (l < r) {
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum == target) {
                        list.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        // 去重，以nums[i]开头的四元组中不再包含当前值
                        while(l < r && nums[l + 1] == nums[l]) {
                            l++;
                        }
                        l++;
                        while(l < r && nums[r - 1] == nums[r]) {
                            r--;
                        }
                        r--;
                    } else if (sum < target) {
                        // 说明nums[l]太小，需要找一个更大的元素
                        l++;
                    } else {
                        // 说明nums[n]太大，需要找一个更小的元素
                        r--;
                    }
                }
            }
        }
        return list;
    }
}



标签
algorithm