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 < na, b, c, and d are distinct.nums[a] + nums[b] + nums[c] + nums[d] == targetYou 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]]
Constraints:
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) // skip dup
continue;
for (int j = i + 1; j < n; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) // skip dup
continue;
long twoSum = 0l + nums[i] + nums[j];
for (int k = j + 1, l = n - 1; k < l;) { // 2 ptr
long sum = twoSum + nums[k] + nums[l];
if (sum == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
k++;
l--;
while (k < l && nums[k] == nums[k - 1]) // skip dup
k++;
while (k < l && nums[l] == nums[l + 1]) // skip dup
l--;
} else if (sum < target)
k++;
else
l--;
}
}
}
return ans;
}
}