4 Sum

Given an array S of n integers, are there elementsa,b,c, and d in S such that a+b+c+d= target? Find all unique quadruplets in the array which gives the sum of target.

Note:The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

分析

1. we use the logic based on two pointers
2. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array
3. Meanwhile, we need to skip equal elements to avoid duplicates

图解

代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums.length < 4) return result;
        Arrays.sort(nums);

        for(int i = 0; i<nums.length-3; i++){
            if(i > 0 && nums[i]==nums[i-1]) continue; // i 至少从 i = 0之后的index开始查重
             for(int j = i+1; j<nums.length-2; j++){
                 if(j > i+1 && nums[j]==nums[j-1]) continue; //  j至少从  = 0之后的index开始查重
                 int k = j+1;
                 int m = nums.length-1;
                 while(k<m){
                     if(nums[i]+nums[j]+nums[k]+nums[m]<target){
                         k++;
                         while(k>0 &&nums[k] == nums[k-1]) k++;
                     }else if(nums[i]+nums[j]+nums[k]+nums[m]>target){
                         m--;
                         while(m>0 &&nums[m] == nums[m+1]) m--;
                     }else{
                         result.add(Arrays.asList(nums[i],nums[j],nums[k],nums[m]));
                         k++;
                         while(k < m  &&nums[k] == nums[k-1]) k++;
                     }
                 }
            }
       }
        return result;
     }
}