Leetcode经典题19--三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

输入输出示例

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

解释：

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意，输出的顺序和三元组的顺序并不重要。

解决方案

方式一：排序 + 双指针

算法思想

第一步：降低复杂度

「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：

第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；

第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说，我们枚举的三元组 (a,b,c) 满足 a≤b≤c，保证了只有 (a,b,c) 这个顺序会被枚举到，而 (b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。

第二步：去除重复值

去重的伪代码

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] != nums[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)

如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。

当第二重循环往后枚举一个元素 b′时，由于 b′>b，那么满足 a+b′+c′=0 的 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] != 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)

实现代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n=nums.length;
        Arrays.sort(nums);//对数组进行排序
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        //枚举三元组的第一个元素
        for(int first=0;first<n;++first){
            //需要去重
            if(first>0&&nums[first]==nums[first-1]){
                continue;
            }
            //三元组的第三个数对应的指针初始值为数组的最右端
            int third=n-1;
            int target=-nums[first];
            //枚举数组中的第二个数
           for(int second=first+1;second<n;++second){
            //去重
            if(second>first+1&&nums[second]==nums[second-1]){
                continue;
            }
            //b的指针在c的左侧
            while(second<third&&nums[second]+nums[third]>target){
                --third;//如果两数之和较大，指针左移
            }
            // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if(nums[second]+nums[third]==target){
                    List<Integer> list=new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
           }
        }
        return ans;
    }
}

复杂度分析

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

空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 O(N)。