526互联

三数之和--双指针

发布时间 2023-09-06 11:38:16作者: 无荔枝

要求找到所有「不重复」且和为 0 的三元组

排序 + 双指针（双指针只在有序时可以用）

有序的另一个作用是辅助去重，比如a,b,c//b,c,a//c,a,b对本题来说是一样的，有序后就只有a,b,c

同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复，因此：

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，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系，时间复杂度从n^2降低到了n，因为每次b往右挪，c会接着上次的往左挪，而不是从最右边开始从头挪(b变大，c只会变小)，等挪到相等就已遍历完，两个指针总计挪了n个位置

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) {
        List<List<Integer>> al = new ArrayList<List<Integer>>();
        //HashSet<Integer> h =new HashSet<Integer>();
        //不能用Hash，因为数组中可能有下标不同但数值相同的，不能简单去重
        Arrays.sort(nums);
        for(int i = 0;i<nums.length-2;i++){
            if(i==0||nums[i]!=nums[i-1]){
                int r = nums.length-1;
                for(int j=i+1;j<nums.length-1;j++){
                    if(j==i+1||nums[j]!=nums[j-1]){
                        while(nums[i]+nums[j]+nums[r]>0&&j<r){//保证右指针不会超过左指针
                            r--;
                        }
                        if(nums[i]+nums[j]+nums[r]==0&&j!=r){//避免左右指针重合的情况
                            List<Integer> t = new ArrayList<Integer>();
                            t.add(nums[i]);
                            t.add(nums[j]);
                            t.add(nums[r]);
                            al.add(t);
                        }
                    }
                }
            }
        }
        return al;
    }
}