Leetcode #18 4Sum

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        //System.out.println(Arrays.toString(nums));
        int len = nums.length;
        List<List<Integer>> result = new LinkedList<>();
        for(int i=0;i<len-3;i++){
            if(i==0||nums[i]!=nums[i-1]){ //去除重复值
                for(int j=i+1;j<len-2;j++){
                    if(j==i+1||nums[j]!=nums[j-1]){
                        int low = j+1,high=len-1;
                        while(low<high){
                            int temp = nums[i]+nums[j]+nums[low]+nums[high];
                            
                            if(temp==target){
                                result.add(Arrays.asList(nums[i],nums[j],nums[low],nums[high]));
                                while(low<high&&nums[low]==nums[low+1]) low++;
                                while(low<high&&nums[high]==nums[high-1]) high--;
                                low++;
                                high--;
                            }
                            else if(temp<target){
                                
                                low++;
                            }
                            else{
                                
                                high--;
                            }
                        }
                    }
                }
            }
        }
        return result;

类似这种k-sum的题，都简化为sorted array的2sum问题，即利用two pointers， 一个头，一个尾，互相逼近看是否达到target值。
3-sum问题即，先选定一个，再在剩余数组中做2-sum，4-sum同上。注意代码中注释的如何去除重复值。
类似题目
2-sum：

public int[] twoSum(int[] nums, int target) {
       Map<Integer, Integer> map = new HashMap<>();
       int[] res = new int[2];
       for(int i=0,len=nums.length;i<len;i++){
           if(map.containsKey(target-nums[i])){
               res[1]=i;
               res[0]=map.get(target-nums[i]);
               return res;
           }
           map.put(nums[i],i);
       }
       return res;
   }

3-sum：

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        Arrays.sort(nums);
        for(int i=0,len=nums.length;i<len-2;i++){
            if(i==0||nums[i]!=nums[i-1]){
                int low =i+1,high=nums.length-1;
                while(low<high){
                    int temp = nums[i]+nums[low]+nums[high];
                    if(temp==0){
                        result.add(Arrays.asList(nums[i],nums[low],nums[high]));
                        while(low<high&&nums[low]==nums[low+1]) low++;
                        while(low<high&&nums[high]==nums[high-1]) high--;
                        low++;
                        high--;
                    }
                    else if(temp>0){
                        high--;
                    }
                    else low++;
                }
            }
        }
        
        return result;
    }

3-sum closer：

Arrays.sort(nums);
        int cur = 0,dis=Integer.MAX_VALUE;
        for(int i=0,len=nums.length;i<len-2;i++){
            if(i==0||nums[i]!=nums[i-1]){
                int low = i+1,high=nums.length-1;
                while(low<high){
                    int temp = nums[i]+nums[low]+nums[high];
                    int d = Math.abs(temp-target);
                    //cur = d<dis?temp:cur;
                    if(temp==target) return target;
                    else if(temp>target){
                        high--;
                    }
                    else{
                        low++;
                    }
                    //System.out.println(d+" "+dis);
                    if(d<dis){
                        dis=d;
                        cur=temp;
                    }
                    //cur = d<dis?temp:cur;
                    //System.out.println(cur);
                }
            }
        }
        return cur;