三数之和

发表于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

LeetCode每日一题，15.3Sum

先看题目描述

大意就是给定一个整数数组 nums，返回所有满足 a + b + c = 0 的三元组 [a, b, c]

算法和思路

这道题想要找出满足条件的三元组不难，难得是去重。我一开始的思路是遍历每个数，然后对于每个数，三元组中的剩下两个只能在 nums 数组它之后的数里找，为了去重，我定义了一个长度为 max - min + 1 的 count 数组，其中 max 和 min 分别是 nums 数组的最大值和最小值，count 数组用来记录 nums 数组里每个值的出现次数，当某个值已使用过后，便将其 count 值 - 1，或者已遍历了某数后，也将其减一，表示之后不会用到，算法源码如下

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
import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        if (nums.length < 3 ) return res;
        int max = 0;
        int min = 10000;
        for (int num: nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        int[] count = new int[max - min +1];
        for (int num: nums) {
            count[num - min]++;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] <= -min && nums[i] + nums[j] >= -max) {
                    count[nums[i] - min]--;
                    count[nums[j] - min]--;
                    if (count[-(nums[i] + nums[j]) - min] > 0) {
                        List<Integer> three = new LinkedList<>();
                        three.add(nums[i]);
                        three.add(nums[j]);
                        three.add(0 - nums[i] - nums[j]);
                        Collections.sort(three);
                        if (!res.contains(three)) res.add(three);
                    }
                    count[nums[i] - min]++;
                    count[nums[j] - min]++;
                }
            }
            count[nums[i] - min]--;
        }
        return res;
    }
}

不过这个运行效率很低，在用例很长时通过不了，后来看题解才想明白另外一个办法

关键是排序和双指针

算法流程：

  • 定义结果数组 res

  • 如果数组长度小于3，直接返回 []

  • 对数组进行升序排序

  • 遍历排序后数组

    • 若 nums[i] > 0，因为已经按升序排序好，后面不可能再出现三数相加等于 0，故直接返回结果
    • 若 nums[i] = nums[i - 1]，则跳过，避免出现重复解
    • 令左指针 left = i + 1，右指针 right = n - 1，当 left < right时，执行循环：
      • 若 left - i >= 2 且 nums[left] = nums[left - 1]，则直接将 left 右移，避免出现重复解
      • 若 nums[right] = nums[right + 1]，则直接将 right左移，避免出现重复解
      • 若 nums[left] + nums[right] + nums[i] = 0，则将这组解添加到 res 数组中，然后left 右移，right 左移
      • 若 nums[left] + nums[right] + nums[i] > 0，表明 nums[right] 偏大，则将 right 左移
      • 若 nums[left] + nums[right] + nums[i] < 0，表明 nums[left] 偏小，则将 left 右移

  • 最终返回 res

感觉自己一开始的那个思路十分混乱，而且过不了检测，关键是没想到先将 nums 数组排序，将 nums 数组排序后，就好想很多，去重也十分简单，思路也很清晰，代码可读性也好不少，感觉自己在做题时不能钻牛角尖，得转换思路

根据这个算法实现的源码如下

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
import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        if (nums.length < 3 ) return res;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i >= 1 && nums[i] == nums[i - 1]) continue;
            if (nums[i] > 0) break;
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (left - i >= 2 && nums[left] == nums[left - 1] ) {
                    left++;
                    continue;
                }
                if (right < nums.length - 1 && nums[right] == nums[right + 1]) {
                    right--;
                    continue;
                }
                if (nums[i] + nums[left] + nums[right] == 0) {
                    List<Integer> three = new LinkedList<>();
                    three.add(nums[i]);
                    three.add(nums[left]);
                    three.add(nums[right]);
                    res.add(three);
                    left++;
                    right--;
                } else if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                }
            }
        }
        return res;
    }
}