leetcode 15 三数之和

目录

 误区：

双指针法：

 误区：

   经历上一题两数之和的经验后，这题很快也想到用哈希。 这题的target为0  通过一个两层for循环将a+b以及ab的值存储起来，再遍历一次数组。 又回到了两数之和的问题。但是出现了一个问题，两数之和只需要返回一个答案即为正确，但是这道题需要返回所有且不重复的答案，问题就出现在去重上。比如[-1,-1,0,1]，答案本应该是只有一组，如果用哈希法就会将两个不同位置的－1作为两组答案输出出去，就会产生重复的三元组。

双指针法：

  这里采用双指针加去重的方法。首先将无序的数组进行排序

 第一个i表示当前for循环中遍历的数字  即为a

left指向当前遍历的下一位 i+1，即为b

right指向的为数组的最后一位 即为c

由于数组经历过排序

1.  a[i]+a[left]+a[right]<0  说明三数相加小了,左指针右移
2. a[i]+a[left]+a[right]<0  说明三数相加大了,右指针左移
3. a[i]+a[left]+a[right]=0  说明三数相加符合,存储为一个三元组

循环的中止条件为left=right，此时b和c重合，没有三个数，即跳出循环，遍历下个a

 while (left < right)    //left=right即无意义,变为两数相加
                {
                    if (nums[i] + nums[left] + nums[right] < 0) {
                        left++;  //说明数选小了 b得变大一些
                    }
                   else if (nums[i] + nums[left] + nums[right] > 0) {
                        right--; //说明数选大了 c得变小一些
                    } else {
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        //将第一组合适的结果放入结果集中
                     
                        }
                        left++;
                        right--;
                        //寻找下一组合适的b和c
                    }
                }

去重问题：

对于a的去重，我们需要保证遍历这个数之前不能存在相同的数

if (i>=1&&nums[i] == nums[i - 1]) {
    continue;  //去除重复的a 
}

不能用nums[i]==nums[i+1] 去重，因为如果此时b也等于a，就去除了一种情况比如上图的[-1,-1,2]，三元组里可以存在相同的元素，但是不能存在相同的三元组，因为必须和前一位a进行比较，如果上一次的a和这次相同，则跳过这次遍历。

对于b和c的去重也是同理

while (right>left&&nums[left] == nums[left + 1]) {
    left++;  //去除重复的b
}
while (right>left&&nums[right] == nums[right - 1]) {
    right--;  //去除重复的c
}

如果左右指针移动的下一位仍然是相同的，则再移动一位，直到循环终止或者移动的下一位不相同为止。但是去重b和c之前需要保存一组数据，如果先去重再保存有可能导致保存不到合适的数据，比如[0,0,0,0,0]这组。

结合思想，完整代码如下

 class Solution {
        public List<List<Integer>> threeSum(int[] nums) {  ArrayList<List<Integer>> result = new ArrayList<>();
            Arrays.sort(nums);  //将数组先排序
            for (int i = 0; i < nums.length; i++) {
                int left = i + 1;
                int right = nums.length-1;
                if (nums[i] > 0) {//第一个数a都大于0 b和c都比a大，所以直接返回  剪枝操作
                    break;
                }
                if (i>=1&&nums[i] == nums[i - 1]) {
                    continue;  //去除重复的a 不能用[i=i+1];
                }
                while (left < right)    //left=right即无意义,变为两数相加
                {
                    if (nums[i] + nums[left] + nums[right] < 0) {
                        left++;  //说明数选小了 b得变大一些
                    }
                    else if (nums[i] + nums[left] + nums[right] > 0) {
                        right--; //说明数选大了 c得变小一些
                    } else {
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        //将第一组合适的结果放入结果集中
                        while (right>left&&nums[left] == nums[left + 1]) {
                            left++;  //去除重复的b
                        }
                        while (right>left&&nums[right] == nums[right - 1]) {
                            right--;  //去除重复的c
                        }
                        left++;
                        right--;
                        //寻找下一组合适的b和c
                    }
                }
            }
            return result;
        }
    }

总结：

注意去重和剪枝的细节以及双指针思想