题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
解题思路
借鉴三数之和的思路，首先将数组从大到小排序，然后从数组首位置开始遍历：
- 固定第一个数，将其加入结果集合，为了避免重复，若该数与前一个数相同则跳过
- 接着固定第二个数为第一个数的下一个位置，将其加入结果集合，同样为了避免重复，若该数与前一个数相同则跳过
- 用双指针法，左右指针分别指向第二个数的下一个位置和最后一个位置，算出两数的目标和，若两位置的数之和正好等于目标，则加入到结果集合中，并将左指针指向右边第一个与当前数不相同的位置，同时右指针向左移动一位；若两位置的数之和小于目标，则将左指针向右移动一位；若两位置的数之和大于目标，则将右指针向左移动一位。这样移动直到左指针超过右指针或与其相遇
- 根据回溯法的思想，遍历完第一个数和第二个数的解之后，分别将其弹出结果集合
代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
vector<int> temp;
int size = nums.size();
for(int i = ; i < size - ; i++){
if(i && nums[i] == nums[i - ]) continue;
int sum3 = target - nums[i];
temp.push_back(nums[i]);
for(int j = i + ; j < size - ; j++){
if(j != i + && nums[j] == nums[j - ]) continue;
int sum2 = sum3 - nums[j];
temp.push_back(nums[j]);
int left = j + , right = size - ;
while(left < right){
if(nums[left] + nums[right] == sum2){
temp.push_back(nums[left]);
temp.push_back(nums[right]);
res.push_back(temp);
temp.pop_back();
temp.pop_back();
left++;
while(nums[left] == nums[left - ]) left++;
right--;
}
else if(nums[left] + nums[right] < sum2)
left++;
else right--;
}
temp.pop_back();
}
temp.pop_back();
}
return res;
}
};