本文共 4585 字,大约阅读时间需要 15 分钟。
Given an array nums
of n integers, are there elements a, b, c in nums
such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []Output: []
Example 3:
Input: nums = [0]Output: []
Constraints:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
题意:给出一个包含 n
个整数的数组 nums
,判断 nums
是否存在三个元素 a, b, c
,使得 a + b + c = 0
。找出所有满足条件、且不重复的三元组。
思路1 排序+双指针+set去重
先排序,然后固定每个数 nums[i]
,在 nums[i+1:size()-1]
的范围内双指针搜索,寻找和为 -nums[i]
的两个元素,找到后插入集合中去重。最后返回结果:
class Solution { public: vector> threeSum(vector & nums) { if (nums.size() < 3) return { }; set > ans; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { int x = nums[i], val = 0 - x, f = i + 1, e = nums.size() - 1; while (f < e) { if (nums[f] + nums[e] > val) --e; else if (nums[f] + nums[e] < val) ++f; else { ans.insert({ x, nums[f], nums[e]}); ++f, --e; } } } vector > res(ans.begin(), ans.end()); return res; }};
效率很低:
执行用时:3084 ms, 在所有 C++ 提交中击败了5.00% 的用户内存消耗:178 MB, 在所有 C++ 提交中击败了5.00% 的用户
思路2 排序+双指针+去重优化
思考发现,如果避免使用集合去重,可以大大降低时间复杂度。我们的做法是:使用连续重复元素的第一个元素,然后在后续区间内进行双指针;得到某一个解后,跳过已经使用的解元素;双指针移动时跳过无用的重复元素。这种做法,既顾及到了可能出现重复元素的三元组如 [2, 2, -4]
,也考虑到了重复使用同一元素的问题,而且避免了多次得到重复三元组:
- 假设数
x
重复了k
次,我们不必要执行k
次两数之和然后去重。对于重复的数,我们只需要找到该数第一次出现的位置:if (i > 0 && nums[i] == nums[i-1]) continue
就可以让我们跳过第2, 3,..., k
次访问同一个数的情况。 - 这里的去重思路是:第一个数的三数之和的解,必然包括它之后相同的数的三数之和解。于是我们只需要得到连续重复元素序列中第一个数的解即可。
具体代码如下:
class Solution { public: vector> threeSum(vector & nums) { if (nums.size() < 3) return { }; vector > ans; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; //使用连续重复元素的第一个 int newTarget = -nums[i], lo = i + 1, hi = nums.size() - 1; //三数变两数 while (lo < hi) { if (nums[lo] + nums[hi] == newTarget) { ans.push_back({ nums[i], 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] < newTarget) ++lo; else --hi; } } return ans; }};
效率如下:
执行用时:144 ms, 在所有 C++ 提交中击败了31.17% 的用户内存消耗:19.8 MB, 在所有 C++ 提交中击败了39.40% 的用户
更多优化如下:
- 不符合条件时,在
lo
或者hi
移动时跳过重复元素; - 如果当前的固定数
nums[i]
和后续数组最小的两个数nums[i + 1], nums[i + 2]
相加,结果大于零,说明后面已经没有结果,直接退出; - 如果当前的固定数
nums[i]
和后续数组最大的两个数nums[size - 1], nums[size - 2]
相加,结果小于零,跳过此次双指针搜索。
class Solution { public: vector> threeSum(vector & nums) { if (nums.size() < 3) return { }; vector > ans; sort(nums.begin(), nums.end()); const int n = nums.size(); for (int i = 0; i < n - 2; ++i) { //只搜索到倒数第三个数为止 if (i > 0 && nums[i] == nums[i - 1]) continue; //去重剪枝,使用连续重复元素的第一个 if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break; //后续循环不会有解 if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue; //本次循环不会有解 int newTarget = -nums[i], lo = i + 1, hi = nums.size() - 1; //三数变两数 while (lo < hi) { if (nums[lo] + nums[hi] == newTarget) { ans.push_back({ nums[i], 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] < newTarget) { while (lo < hi && nums[lo] == nums[lo + 1]) ++lo; //跳过无用的重复值 ++lo; } else { while (lo < hi && nums[hi] == nums[hi - 1]) --hi; //跳过无用的重复值 --hi; } } } return ans; }};
结果如下:
执行用时:112 ms, 在所有 C++ 提交中击败了62.12% 的用户内存消耗:19.8 MB, 在所有 C++ 提交中击败了34.94% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108933546 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!