18 4Sum
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
和 3 sum 类似，排序后， 固定前 2 个点，然后剩下的部分两个指针向中间移动。固定的两个点和移动的两个点都需要去重。
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ret=new LinkedList<>();
Arrays.sort(nums);
int len=nums.length;
for(int i=0;i<len-3;++i){
if(i>0 && nums[i]==nums[i-1]) continue;
for(int j=i+1;j<len-1;++j){
if(j!=i+1 && nums[j]==nums[j-1]) continue;
int left=j+1, right=len-1;
int total=target-nums[i]-nums[j];
while(left<right){
int sum=nums[left]+nums[right];
if(sum<total){
left++;
} else if(sum>total){
right--;
} else {
ArrayList<Integer> list = new ArrayList<>(4);
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
ret.add(list);
left++;
while(left<right && nums[left]==nums[left-1]) left++;
right--;
while(left<right && nums[right]==nums[right+1]) right--;
}
}
}
}
return ret;
}