15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //三者都不相同，和为0
        //可以作为i》j》k   不影响的 
        //可能有多个
 
        //暴力法  3层循环，有点bt
        //借用哈希表，变为2层循环
 
 
        //会有去重问题
        //可以进一步思考-》nums[i]<=nums[j]<=nums[k]
        //进一步思考-》可以先将数组就行排序
        //还是有去重问题，此题不适合哈希表法，适合双指针
 
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        
 
        for(int i=0;i<nums.length;){
            int left=i+1;
            int right=nums.length-1;
 
            while(left<right){
                if(nums[i]+nums[left]+nums[right]==0){
                    List<Integer> l=new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[left]);
                    l.add(nums[right]);
                    ans.add(l);
 
                    int y=nums[left];
                    left++;
                    while(left<right && nums[left]==y){
                        left++;
                    }
                }else if(nums[i]+nums[left]+nums[right]<0){
                    // int y=nums[left];
                    // left++;
                    // while(left<right && nums[left]==y){
                    //     left++;
                    // }
                    left++;
                }else{
                    // int z=nums[right];
                    // right--;
                    // while(left<right && nums[right]==z){
                    //     left--;
                    // }
                    right--;
                }
 
 
            }
 
            int x=nums[i];
            i++;
            while(i<nums.length && nums[i]==x){
                i++;
            }
 
        }
        
        return ans;
 
 
 
    }
}