1.题目
18. 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[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 = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
2. 解法（排序+双指针）
算法思路：
a. 依次固定⼀个数a ；
b. 在这个数a 的后⾯区间上，利⽤「三数之和」找到三个数，使这三个数的和等于target- a 即可。
【优选算法】——双指针——15. 三数之和-CSDN博客
3.代码实现
C++
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ret; // 1. 排序 sort(nums.begin(), nums.end()); // 2. 利⽤双指针解决问题 int n = nums.size(); for (int i = 0; i < n;) // 固定数 a { // 利⽤ 三数之和 for (int j = i + 1; j < n;) // 固定数 b { // 双指针 int left = j + 1, right = n - 1; long long aim = (long long)target - nums[i] - nums[j]; while (left < right) { int sum = nums[left] + nums[right]; if (sum < aim) left++; else if (sum > aim) right--; else { ret.push_back( {nums[i], nums[j], nums[left++], nums[right--]}); // 去重⼀ while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } } // 去重⼆ j++; while (j < n && nums[j] == nums[j - 1]) j++; } // 去重三 i++; while (i < n && nums[i] == nums[i - 1]) i++; } return ret; } };
