三数之和[中等]

有了这样的发现，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针，从而得到下面的伪代码：

nums.sort()
for first = 0 .. n-1
    if first == 0 or nums[first] != nums[first-1] then
        // 第三重循环对应的指针
        third = n-1
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                // 向左移动指针，直到 a+b+c 不大于 0
                while nums[first]+nums[second]+nums[third] > 0
                    third = third-1
                // 判断是否有 a+b+c==0
                check(first, second, third)
1
2
3
4
5
6
7
8
9
10
11
12

这个方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从O(N2)减少至O(N)。为什么是O(N)呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的b），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为O(N)。

注意到我们的伪代码中还有第一重循环，时间复杂度为O(N)，因此枚举的总时间复杂度为O(N2)。由于排序的时间复杂度为O(Nlog⁡N)，在渐进意义下小于前者，因此算法的总时间复杂度为O(N2)。

上述的伪代码中还有一些细节需要补充，例如我们需要保持左指针一直在右指针的左侧（即满足b≤c），具体可以参考下面的代码，均给出了详细的注释。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //思想：1、先对 nums 进行排序
        // 2、先确定第一层循环，通过 0 - nums[x] 得到第二层和第三层的和
        // 3、将第二层和第三层汇总为一层，left = i + 1; right = nums.length - 1; 进行双指针移动，计算和，如果相等，加入队列，并继续移动指针，直到不满足 left < right
        int left = 0, right = 0, size = 0;
        List<List<Integer>> res = new ArrayList();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++) {
            if (i > 0 && i < nums.length && nums[i] == nums[i-1]) {
                continue;
            }
            // i 发生变化之后，left 和 right 指针都需要发生变化。 第一次将right定义再外部，导致bug
            left = i + 1;
            right = nums.length - 1;
            int tar = -nums[i];
            while(left < right) {
                if (nums[left] + nums[right] == tar) {
                    List<Integer> temp = Arrays.asList(nums[i], nums[left], nums[right]);
                    res.add(temp);
                    // 数据去重
                    while(left < right && nums[left] == nums[left + 1]) {
                        ++left;
                    }
                    while(right > left && nums[right] == nums[right - 1]) {
                        --right;
                    }
                    ++left;
                    --right;
                } else if(nums[left] + nums[right] < tar){
                    ++left;
                } else {
                    --right;
                }
            }
        }
         return res;
    }
}
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

时间复杂度： O(N2)其中N是数组nums的长度。
时间复杂度： O(N2)，其中N是数组nums的长度。