LeetCode 15：三数之和

链接

题目：

思路：排序 + 双指针

nSum 系列问题的核心思路就是排序 + 双指针 ；

为什么两数之和不能用双指针？
双指针需要数组排序，而两数之和需要返回的是索引，排序后索引就乱了 ！

双指针思想：

根据sum的大小调整左右指针 ；

但是，这样实现会造成重复的结果，比如说 nums = [1,1,1,2,2,3,3], target = 4，得到的结果中 [1,3] 肯定会重复；
所以当nums[left]与下一个数nums[left+1]相等则left++跳过，right同理！

注意：
三数之和时，left必须从i+1开始，否则双指针时会重复使用num[i] ！

Java实现：

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
    
        // 返回的是数而不是索引 ！
        List<List<Integer>> r=new ArrayList<>();
        if(nums.length==0){
    
            return r;
        }
        // 1.先排序
        Arrays.sort(nums);

        for(int i=0;i<nums.length;i++){
    
            // 去重1
            if(i>0 && nums[i]==nums[i-1]){
    
                continue; // 遍历下一个 i
            }
            // 如果i>0，而数组又是递增的，则注定无法凑出0 ！
			if(nums[i]>0){
    
                continue;
            }
            // 2.双指针找为0-nums[i]的两个数， 
            int target=0-nums[i];
            int left=i+1; // left必须从i+1开始，否则会重复使用num[i] ！
            int right=nums.length-1;
            while(left<right){
    
                int sum=nums[left]+nums[right];
                // 根据sum来调整指针
                if(sum>target){
    
                    right--;
                }else if(sum<target){
    
                    left++;
                }else if(sum==target){
    
                    r.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    // 去重2：第一次添加到List后就要去重！
                    while(left<right && nums[left]==nums[left+1]){
    
                        left++;
                    }
                    while(left<right && nums[right]==nums[right-1]){
    
                        right--;
                    }
                    // 继续寻找
                    right--;
                    left++;
                }
            }
        }
        return r;
    }
}