LeetCode——三数之和

矫情吗；* 2022-12-13 01:51 126阅读 0赞

## **题目** ##

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = \[-1, 0, 1, 2, -1, -4\]，

满足要求的三元组集合为：

[
      [-1, 0, 1],
      [-1, -1, 2]
    ]

## **题解** ##

从题目中可以获取以下几条信息：

1.  数组元素为int类型，无序，数组元素可重复
2.  找到所有满足条件且不重复的三元组，意思是说结果可能为多个。不重复要求结果要去重，比如\[-1, 0, 1\]与\[0, 1, -1\]其实是一个结果。

## **解题思路** ##

### 方法一：暴力搜索法 ###

使用三层循环来枚举三元组，这样我们就能得到满足要求的所有三元组，时间复杂度为![O(n^\{3\})][O_n_3]，之后我们还需要使用哈希表对结果进行去重操作以便得到不重复的三元组，会消耗大量的空间。因此该方法时间复杂度和空间复杂度将会很高。

### 方法二：排序+双指针法 ###

首先我们先看下重复的三元组是如何产生的，对于数组\[-1, 0, 1, 2, -1, -4\]，满足条件的三元组为

[
        [-1, 0, 1],
        [-1, 2, -1],
        [0, 1, -1]
    ]

其中\[-1, 0, 1\]和\[0, 1, -1\]属于同一个三元组，即重复。很明显重复三元组的产生是因为数组无序且包含重复元素，所以在遍历时才会产生(a, b, c)和(b, a, c)的这样的组合。既然是这样，我们就可以把数组按从小到大顺序排序，同时，对于每一层循环，相邻两次枚举的元素不同，使得在遍历的时候满足![a\\leq b\\leq c][a_leq b_leq c]，保证只有(a,b,c)这样的组合产生而不会产生(b,a,c)这样的组合即可。举个例子，对于数组\[0, 1, 2, 2, 2, 3\]，使用三层循环遍历得到第一个三元组为(0, 1, 2)，如果第三层的循环继续枚举到下一个元素，仍然是三元组(0, 1, 2)，产生了重复。因此我们需要将第三层循环跳过重复元素直接到下一个不同的元素，即数组中的最后一个元素3，枚举三元组(0, 1, 3)。相应的伪代码如下：

nums.sort()
    for first = 0 .. n-1
        // 只有和上一次枚举值不相同才进行枚举
        if first==0 or nums[first]!=nums[first-1] then 
            for second = first+1 .. n-1
                // 同理，只有和上一次枚举值不相同才进行枚举
                if second==first+1 or nums[second]!=second[second-1] then
                    for third = second+1 .. n-1
                        // 同理，只有和上一次枚举值不相同才进行枚举
                        if third=second+1 or nums[third]!=nums[third-1] then
                            // 判断是否有 a+b+c=0
                            check(first, second, third)

这种方法的时间复杂度依然是![O(n^\{3\})][O_n_3]，原因是我们依然使用的是三层循环。

### 优化 ###

下面我们将再此基础上进行优化，可以发现，如果我们固定了前两层循环枚举到的元素值a和b，那么对于第三层循环就只有唯一的c满足a+b+c=0。而且当第二层循环让后枚举一个元素值b’时，由于b’>b，那么满足a+b’+c’=0的c’一定有c’<c，即c’在数组中一定出现在c的左侧。于是我们就可以在从小到大枚举b的同时从大到小枚举c，即第二层循环和第三层循环可以并列执行。

有了这样的发现，我们就可以保持第二层循环不变，将第三层循环编程一个从右端开始向左移动的指针。伪代码如下：

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]!=second[second-1] then
                    while nums[first]+nums[second]+nums[third] > 0
                        third = third-1
                    // 判断是否有 a+b+c=0
                    check(first, second, third)

这个方法就是我们常说的“双指针”，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素时递减的，那么就可以使用双指针方法，将枚举的时间复杂度从![O(n^\{2\})][O_n_2]减少至![O(n)][O_n]。

### 具体代码实现 ###

class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            // 排序
            Arrays.sort(nums);
    
            List<List<Integer>> results = new ArrayList<List<Integer>>();
            // 枚举a
            for (int first=0; first<nums.length-2; ++first) {
                // 保证和上次枚举的元素值不同
                if (first>0 && nums[first]==nums[first-1]) {
                    continue;
                }
                // c 对应的指针初始位置为数组最右端
                int third = nums.length-1;
                for (int second=first+1; second<nums.length-1; ++second) {
                    // 保证和上次枚举的元素值不同
                    if (second>first+1 && nums[second]==nums[second-1]) {
                        continue;
                    }
                    // 需要保证b的指针在c的只针的左边
                    while (second<third && nums[first]+nums[second]+nums[third] > 0) {
                        --third;
                    }
                    // 如果两指针重合，随着b指针的增加就不会有满足a+b+c=0且b<c的c了，此时可以直接退出循环
                    if (second==third) {
                        break;
                    }
                    if (nums[first]+nums[second]+nums[third]==0) {
                        List<Integer> result = new ArrayList<Integer>();
                        result.add(nums[first]);
                        result.add(nums[second]);
                        result.add(nums[third]);
                        results.add(result);
                    }
                }
            }
            return results;
        }
    }

## **复杂度分析** ##

时间复杂度：![O(n^\{2\})][O_n_2]，其中n为数组nums的长度

空间复杂度：![O(logn)][O_logn]，忽略存储答案的空间，排序的空间复杂度为![O(logn)][O_logn]。这种情况下我们修改了输入的数组nums，实际情况可能不一定允许，因此也可以看成使用了一个额外的数据存储了nums的副本进行排序，空间复杂度为![O(n)][O_n]

## **小结** ##

当我们确定第一层的枚举值c之后，接下来就可以看做是求解两数之和等于-c的问题了

[O_n_3]: https://private.codecogs.com/gif.latex?O%28n%5E%7B3%7D%29
[a_leq b_leq c]: https://private.codecogs.com/gif.latex?a%5Cleq%20b%5Cleq%20c
[O_n_2]: https://private.codecogs.com/gif.latex?O%28n%5E%7B2%7D%29
[O_n]: https://private.codecogs.com/gif.latex?O%28n%29
[O_logn]: https://private.codecogs.com/gif.latex?O%28logn%29