Given an array nums of n integers and an integer target , are there elements a, b, c, and d in nums such that a + b + c + d = target ? Find all unique quadruplets in the array which gives the sum of target .
Notice that the solution set must not contain duplicate quadruplets.
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 = [], target = 0 Output: []Constraints:
0 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target ，找出所有相加等于 target 且不重复的四元组。
如果这就是面试题，我们必须思考：
数组索引从 0 还是从 1 开始；没有解的时候怎么办，返回异常吗；是否有唯一解；有多个解的时候，返回哪一个解；是否能够使用同一个元素两次；……本题的题目和示例给出了解答：可能没有解，返回空向量，也可能有一个或多个解；不能返回重复的四元组；同一个元素不能使用多次。
通过固定一个数 nums[i] ，可以将四元组的问题转换为三元组，使用前面的代码。同样，为了避免使用集合去重，做法是：使用连续重复元素的第一个元素，然后在后续区间内进行双指针；得到某一个解后，跳过已经使用的解元素；双指针移动时跳过重复的元素。这种做法，既顾及到了可能出现重复元素的四元组 ，也考虑到了重复使用同一元素的问题，而且避免了多次得到重复四元组。
还用到了更多的优化：
不符合条件时，在 lo 或者 hi 移动时跳过重复元素；如果当前的固定数和后续数组最小的几个数相加，结果大于零，说明后面已经没有结果，直接退出；如果当前的固定数和后续数组最大的几个数相加，结果小于零，跳过此次双指针搜索。 class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { if (nums.size() < 4) return {}; vector<vector<int>> ans; sort(nums.begin(), nums.end()); //首先排序 const int n = nums.size(); for(int i = 0; i < n - 3; ++i) { //只遍历到倒数第四个数为止 if (i > 0 && nums[i] == nums[i - 1]) continue; //去重优化,使用连续重复元素的第一个 if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; //后续没有解 if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; //本次无解 int newTarget = target - nums[i]; // 将四数之和转化为三数之和 for (int j = i + 1; j < n - 2; ++j) { //只遍历到倒数第三个数为止 if (j > i + 1 && nums[j] == nums[j - 1]) continue; //去重优化,使用连续重复元素的第一个 if (nums[j] + nums[j + 1] + nums[j + 2] > newTarget) break; //后续没有解 if (nums[j] + nums[n - 2] + nums[n - 1] < newTarget) continue; //本次无解 int newTarget2 = newTarget - nums[j], lo = j + 1, hi = n - 1; //三数之和变成两数之和 while (lo < hi) { //两数之和直接套用代码 if (nums[lo] + nums[hi] == newTarget2) { ans.push_back({nums[i], nums[j], nums[lo], nums[hi]}); while (lo < hi && nums[lo] == nums[lo + 1]) ++lo; //注意去重 while (lo < hi && nums[hi] == nums[hi - 1]) --hi; ++lo, --hi; } else if (nums[lo] + nums[hi] < newTarget2) { while (lo < hi && nums[lo] == nums[lo + 1]) ++lo; ++lo; } else { while (lo < hi && nums[hi] == nums[hi - 1]) --hi; --hi; } } } } return ans; } };效率是可喜的：
执行用时：20 ms, 在所有 C++ 提交中击败了92.45% 的用户 内存消耗：12.8 MB, 在所有 C++ 提交中击败了5.02% 的用户