[数组]15. 3Sum

15. 3Sum
题目大意
给定一个数组，要求找出所有和为0的三个数的集合，不能重复。

双指针法
空间:O(n) 时间:O(n^2)
Youtube 讲解
闭着眼睛也要记得的解法

// [nums[i], low, high] = 0

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); //一定要sort
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i< nums.length -2; i++){
            if(i> 0 && nums[i-1] == nums[i]) continue; //去重nums[i]
            int low = i+1;
            int high = nums.length-1;
            int sum = 0 - nums[i];//即 从这里开始是low和high的two sum
            while(low < high){
                if(nums[low] + nums[high] == sum){ //找到了
                    res.add(Arrays.asList(nums[i],nums[low],nums[high]));  //记住 Array.aslist()这种方法！！
                    while(low < high && nums[low+1] == nums[low] ) low++;//去重nums[low]
                    while(low < high && nums[high -1] == nums[high]) high--;//去重nums[high]
                    low ++;
                    high--;
                }else if(nums[low] + nums[high] < sum){
                    low++;
                }else high --;
            }
        }
        return res;
        
        
    }
}