力扣（15.18）补9.19

15.三数之和

我以为不会太难，md不会。

 其实很让我惊讶的是，双指针用了2层循环但复杂度确是O（n）。牛🐮🐮🐮🐮🐮🐮🐮🐮🐮🐮🐮

另外这题除了算法思想，也有很多细节要处理，炒鸡花时间。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        for(int first=0;first<n-2;first++){
            int second=first+1,third=n-1,target=-nums[first];
            if((first>0&&nums[first]==nums[first-1])||nums[first]>0)
            continue;
            for(;second<third;second++){
                if(second>first+1&&nums[second]==nums[second-1])
                    continue;           
            while(third>second&&nums[second]+nums[third]>target){
                third--;
            }
            if(third==second)
            break;
            // System.out.println(first+" "+second+" "+third);
                if(nums[second]+nums[third]==target){                 
                    List<Integer> list=new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
               
            }
        }
        return ans;

    }
}

18.四数之和

这题难度更大，但思路和三路之和一样，双指针简化一层循环。

class Solution {

    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> ans=new ArrayList<>();

        Arrays.sort(nums);

        int n=nums.length;

        if(n<=3)

        return ans;

        for(int a=0;a<nums.length-3;a++){

            if(a>0&&nums[a]==nums[a-1])

            continue;

            for(int b=a+1;b<n-2;b++){

                if(b>a+1&&nums[b]==nums[b-1])

                continue;

                int c=b+1,d=n-1;

                long target1=(long)target-(long)nums[a]-(long)nums[b];

                while(c<d){

                                       

                    if(nums[c]+nums[d]<target1) c++;

                    if(nums[c]+nums[d]>target1) d--;

                    if(c==d)break;

                    if(nums[c]+nums[d]==target1){

                        List<Integer> list=new ArrayList<>();

                        list.add(nums[a]);

                        list.add(nums[b]);

                        list.add(nums[c]);

                        list.add(nums[d]);

                        ans.add(list);

                    while(c<d&&nums[c]==nums[c+1]) c++;

                    while(c<d&&nums[d]==nums[d-1])d--; 

这俩个循环的位置十分关键，防止出现重复四元组，当四元组不满条件，直接用外面的循环筛掉，当满足条件，不能有重复。

                        c++;d--;

                    }

                }

            }

        }

        return ans;

    }

}