3.三数之和

• 2.6

  • left 和 right 是在锚点的右边 ，创建新ist 是发现了才创建
  • 锚点需要在第二个位置（去重！）

• 1.22

  • 固定锚点-》移动右边的左右指针向中间收敛（必须保证相同的数字跳过！！！包括第一个锚点）
  • 事先排序

• 1.10

  • i 的去重时，应该是在第二个才开始的，也就是 i>0,然后 continue
  • 在左右指针的去重时，必须同时满足左指针小于右指针，然后再判断+1-1是否相等，最后一起收缩
    • “找到答案 → 存下来 → 循环跳过重复值 → 最后指针再走一步”。
    • 固定一个锚点，然后找右边的左右指针满足三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while(left<right){
                if(nums[i]+nums[left]+nums[right]==0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    
                    while(left<right&&nums[left]==nums[left+1]) left++;
                    while(left<right&&nums[right]==nums[right-1]) right--;
                    left++;
                    right--;
 
            }else if(nums[i]+nums[left]+nums[right]>0){
                right--;
            }else{
                left++;
            }
            }
 
        }
        return res;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        //万能的Arrays,对数组都有效
        Arrays.sort(nums);
		//需要排除掉右边两个指针
        for(int i = 0;i<nums.length-2;i++){
            if(i>0&&nums[i]==nums[i-1]){
            //continue跳过for循环
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while(left<right){
 
                if(nums[i]+nums[left]+nums[right]==0){
                //Arrays.asList方法调用
                list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                while(left<right&&nums[left]==nums[left+1]){
                    left++;
                }
                while(left<right&&nums[right]==nums[right-1]){
                    right--;
                }
                left++;
                right--;
            }else if(nums[i]+nums[left]+nums[right]>0){
                right--;
            }else{
                left++;
            }
        }
    }
            
        return list;
    }
}