15. 3Sum

leetcode link

Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:
Input: nums = []
Output: []

Example 3:
Input: nums = [0]
Output: []

思路：排序+双指针。三个数(a,b,c)和为0，先对数组从小到大排序，固定最左边的a, 然后在右边的序列中寻找和为-a的b和c。

nums

怎么找b和c呢？因为数组是有序的，如上图那样，固定了nums[i],让i在最外层循环，left取i+1，right取数组最后一个，要寻找满足nums[left]+nums[right] +nums[i] =0的left和right，在while(left<right)中判断三数之和sum与0的大小关系。等于0装入结果集，小于0 left右移，大于0 right左移。

注意：

1.先解决一下数组长度小于3 和等于3的情况。
2.结果不重复，所以先用Set<List<Integer>>保存结果；
3.最外层i的循环需要判断nums[i] 是否等于nums[i-1], 相等可以直接跳过；
1.如果排序之后最左边的值nums[i] >0,所以不可能后面都是比0大，可以直接跳出循环。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Set<List<Integer>> set = new HashSet<>();
        if(nums.length < 3){
            return result;
        }
        if(nums.length == 3){
            if(nums[0] + nums[1] + nums[2] == 0){
                List<Integer> list = new ArrayList<>();
                list.add(nums[0]);
                list.add(nums[1]);
                list.add(nums[2]);
                result.add(list);
            }
            return result;
        }
        Arrays.sort(nums);
        for(int i=0; i<nums.length-2; i++){
            if(i>0 && nums[i]==nums[i-1]){//从i=1开始判断是否与前一个重复
                continue;
            }
            if(nums[i] > 0){
                break;//后面都是大于0的，没有解了
            }
            int left = i+1;
            int right = nums.length - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    set.add(list);
                }
                if(sum < 0){
                    left++;
                }else{
                    right--;
                }
            }
        }
        for(List<Integer> l : set){
            result.add(l);
        }
        return result;
    }
}