本文共 3039 字,大约阅读时间需要 10 分钟。
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 = 0Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [], target = 0Output: []
Constraints:
0 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
题意:给定一个包含 n
个整数的数组 nums
和一个目标值 target
,找出所有相加等于 target
且不重复的四元组。
如果这就是面试题,我们必须思考:
- 数组索引从
0
还是从1
开始; - 没有解的时候怎么办,返回异常吗;
- 是否有唯一解;
- 有多个解的时候,返回哪一个解;
- 是否能够使用同一个元素两次;
- ……
本题的题目和示例给出了解答:可能没有解,返回空向量,也可能有一个或多个解;不能返回重复的四元组;同一个元素不能使用多次。
思路1 排序+双指针+去重优化
通过固定一个数 nums[i]
,可以将四元组的问题转换为三元组,使用前面的代码。同样,为了避免使用集合去重,做法是:使用连续重复元素的第一个元素,然后在后续区间内进行双指针;得到某一个解后,跳过已经使用的解元素;双指针移动时跳过重复的元素。这种做法,既顾及到了可能出现重复元素的四元组 ,也考虑到了重复使用同一元素的问题,而且避免了多次得到重复四元组。
还用到了更多的优化:
- 不符合条件时,在
lo
或者hi
移动时跳过重复元素; - 如果当前的固定数和后续数组最小的几个数相加,结果大于零,说明后面已经没有结果,直接退出;
- 如果当前的固定数和后续数组最大的几个数相加,结果小于零,跳过此次双指针搜索。
class Solution { public: vector> fourSum(vector & nums, int target) { if (nums.size() < 4) return { }; vector > 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% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108932635 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!