给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0 输出：[]
提示：
0 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
“排序 + 双指针”实现。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n, res = len(nums), []
if n < 4:
return []
nums.sort()
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
k, l = j + 1, n - 1
while k < l:
if nums[i] + nums[j] + nums[k] + nums[l] == target:
res.append([nums[i], nums[j], nums[k], nums[l]])
k += 1
l -= 1
while k < n and nums[k] == nums[k - 1]:
k += 1
while l > j and nums[l] == nums[l + 1]:
l -= 1
elif nums[i] + nums[j] + nums[k] + nums[l] < target:
k += 1
else:
l -= 1
return resclass Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length;
if (n < 4) {
return Collections.emptyList();
}
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int k = j + 1, l = n - 1;
while (k < l) {
if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
++k;
--l;
while (k < n && nums[k] == nums[k - 1]) {
++k;
}
while (l > j && nums[l] == nums[l + 1]) {
--l;
}
} else if (nums[i] + nums[j] + nums[k] + nums[l] < target) {
++k;
} else {
--l;
}
}
}
}
return res;
}
}class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
if (n < 4) {
return {};
}
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int k = j + 1, l = n - 1;
while (k < l) {
if (nums[i] + nums[j] == target - nums[k] - nums[l]) {
res.push_back({nums[i], nums[j], nums[k], nums[l]});
++k;
--l;
while (k < n && nums[k] == nums[k - 1]) ++k;
while (l > j && nums[l] == nums[l + 1]) --l;
} else if (nums[i] + nums[j] < target - nums[k] - nums[l]) {
++k;
} else {
--l;
}
}
}
}
return res;
}
};func fourSum(nums []int, target int) [][]int {
n, res := len(nums), make([][]int, 0)
if n < 4 {
return res
}
sort.Ints(nums)
for i := 0; i < n-3; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
for j := i + 1; j < n-2; j++ {
if j > i+1 && nums[j] == nums[j-1] {
continue
}
k, l := j+1, n-1
for k < l {
if nums[i]+nums[j]+nums[k]+nums[l] == target {
res = append(res, []int{nums[i], nums[j], nums[k], nums[l]})
k++
l--
for k < n && nums[k] == nums[k-1] {
k++
}
for l > j && nums[l] == nums[l+1] {
l--
}
} else if nums[i]+nums[j]+nums[k]+nums[l] < target {
k++
} else {
l--
}
}
}
}
return res
}/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
const n = nums.length;
if (n < 4) return [];
let res = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (let j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
let k = j + 1;
let l = n - 1;
while (k < l) {
if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
res.push([nums[i], nums[j], nums[k], nums[l]]);
++k;
--l;
while (k < n && nums[k] == nums[k - 1]) ++k;
while (l > j && nums[l] == nums[l + 1]) --l;
} else if (nums[i] + nums[j] + nums[k] + nums[l] < target) {
++k;
} else {
--l;
}
}
}
}
return res;
};