【双指针】三数之和

https://leetcode-cn.com/problems/3sum/submissions/

错误代码：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length <= 2) {
            return new ArrayList<List<Integer>>();
        }
        
        Arrays.sort(nums);
        
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        
        for(int i = 0; i < nums.length - 2; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) { //判断外层循环即a, 和上一次枚举的数是否相同
                continue;
            }
            
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right) {
                if(left > i + 1 && nums[left-1] == nums[left] && nums[right+1] == nums[right]) {
                    left++;
                    right--;
                    continue;
                }
                
                if(nums[left] + nums[right] == -nums[i]) {
                    List list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                }
                
                left++;
                right--;
            }
        }
        
        return result;
    }
}

测试用例：

[1,-1,-1,0]

 排序后，出现a的下一个等于上一个，left的下一个和right的下一个相等，所以没有遍历完全。

错误原因：

这是错误的，同时的意思不是(左指针++ && 右指针--)，而是左指针++的同时，找到合适的右指针位置。

        因为当第二重循环往后枚举一个元素 b'时，由于 b' > b，那么满足 a+b'+c'=0的 c'一定有 c' < c即 c' 在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。

        核心理解：当b向右的时候，为了能等于0，c一定是向左的。

        但是c什么时候停止向左呢？当新的三数之和首次小于等于0时立马停止，三数之和大于0时，c才不断减小。

        即：b向右一位，c向左的位数不一定会是一位，但是一定是当新的三数之和首次小于等于0时立马停止。下次b继续向右一位（b变大）时，从当前位置继续判断c的位置即可。

 修正：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length <= 2) {
            return new ArrayList<List<Integer>>();
        }
        
        Arrays.sort(nums);
        
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        
        for(int i = 0; i < nums.length - 2; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) { //判断外层循环即a, 和上一次枚举的数是否相同
                continue;
            }
            
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right) {
                if(left > i + 1 && nums[left-1] == nums[left]) {//和上一次枚举的不同
                    left++;
                    continue;
                }


                while(left < right && nums[right] + nums[left] > -nums[i]) {
                    right--;
                }
                
                if(left == right){
                    break;
                }


                if(nums[left] + nums[right] == -nums[i]) {
                    List list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                }
                
                left++;
            }
        }
        
        return result;
    }
}

总结：

1. 注意不要写出O(N^3)的代码，并且如果真的写出来还要注意去重。
2. 注意内循环中如何确定每次右指针的位置。
3. 实际的时间复杂度为：O(N^2)，N为输入数组长度
4. 空间复杂度为：
   1. 在允许修改输入数组的情况下，为O(logN)，只考虑排序的空间复杂度；
   2. 在不允许修改输入数组的情况下，为O(N)，需要使用了一个额外的数组存储输入数组的副本并进行排序。