微课做动画的网站,seo品牌优化百度资源网站推广关键词排名,托育项目建设背景及必要性,建设网站花都区题目 给你一个包含 n 个整数的数组 nums#xff0c;判断 nums 中是否存在三个元素 a#xff0c;b#xff0c;c #xff0c;使得 a b c 0 #xff1f;请你找出所有满足条件且不重复的三元组。
注意#xff1a; 答案中不可以包含重复的三元组。 示例#xff1a; 给定数…题目 给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 请你找出所有满足条件且不重复的三元组。
注意 答案中不可以包含重复的三元组。 示例 给定数组 nums [-1, 0, 1, 2, -1, -4] 满足要求的三元组集合为 [ [-1, 0, 1], [-1, -1, 2] ] 思路
这道题与前面提到的两数之和以及四数之和Ⅱ在题意上非常类似大家第一想法可能就是使用哈希法来处理但是事实证明哈希解法此时并不是明智的选择。
哈希解法
两层for循环就可以确定 a 和b 的数值了可以使用哈希法来确定 0-(ab) 是否在 数组里出现过其实这个思路是正确的但是我们有一个非常棘手的问题就是题目中说的不可以包含重复的三元组。
把符合条件的三元组放进vector中然后再去重这样是非常费时的很容易超时也是这道题目通过率如此之低的根源所在。
去重的过程不好处理有很多小细节如果在面试中很难想到位。
时间复杂度可以做到O(n^2)但还是比较费时的因为不好做剪枝操作。
哈希法C代码:
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(), nums.end());// 找出a b c 0// a nums[i], b nums[j], c -(a b)for (int i 0; i nums.size(); i) {// 排序之后如果第一个元素已经大于零那么不可能凑成三元组if (nums[i] 0) {break;}if (i 0 nums[i] nums[i - 1]) { //三元组元素a去重continue;}unordered_setint set;for (int j i 1; j nums.size(); j) {if (j i 2 nums[j] nums[j-1] nums[j-1] nums[j-2]) { // 三元组元素b去重continue;}int c 0 - (nums[i] nums[j]);if (set.find(c) ! set.end()) {result.push_back({nums[i], nums[j], c});set.erase(c);// 三元组元素c去重} else {set.insert(nums[j]);}}}return result;}
}; 时间复杂度: O(n^2)空间复杂度: O(n)额外的 set 开销 可以看到剪枝逻辑非常复杂尤其是去重的逻辑判断上所以这里引出更加好理解并且效率高的双指针法。
双指针法
其实这道题目使用哈希法并不十分合适因为在去重的操作中有很多细节需要注意在面试中很难直接写出没有bug的代码。而且使用哈希法 在使用两层for循环的时候能做的剪枝操作很有限虽然时间复杂度是O(n^2)也是可以在leetcode上通过但是程序的执行时间依然比较长 。
这道题目使用双指针法 要比哈希法高效一些那么来讲解一下具体实现的思路。
动画效果如下 拿这个nums数组来举例首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]b nums[left]c nums[right]。
接下来如何移动left 和right呢 如果nums[i] nums[left] nums[right] 0 就说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动这样才能让三数之和小一些。
如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止。
时间复杂度O(n^2)。
C代码代码如下
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(), nums.end());// 找出a b c 0// a nums[i], b nums[left], c nums[right]for (int i 0; i nums.size(); i) {// 排序之后如果第一个元素已经大于零那么无论如何组合都不可能凑成三元组直接返回结果就可以了if (nums[i] 0) {return result;}// 错误去重a方法将会漏掉-1,-1,2 这种情况/*if (nums[i] nums[i 1]) {continue;}*/// 正确去重a方法if (i 0 nums[i] nums[i - 1]) {continue;}int left i 1;int right nums.size() - 1;while (right left) {// 去重复逻辑如果放在这里000 的情况可能直接导致 rightleft 了从而漏掉了 0,0,0 这种三元组/*while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;*/if (nums[i] nums[left] nums[right] 0) right--;else if (nums[i] nums[left] nums[right] 0) left;else {result.push_back(vectorint{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后对b 和 c去重while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;// 找到答案时双指针同时收缩right--;left;}}}return result;}
}; 时间复杂度: O(n^2)空间复杂度: O(1) 注意点
a的去重
说到去重其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]nums[left]nums[right]
a 如果重复了怎么办a是nums里遍历的元素那么应该直接跳过去。
但这里有一个问题是判断 nums[i] 与 nums[i 1]是否相同还是判断 nums[i] 与 nums[i-1] 是否相同。
有人可能想这不都一样吗。
其实不一样
都是和 nums[i]进行比较是比较它的前一个还是比较它的后一个。
如果我们的写法是 这样
if (nums[i] nums[i 1]) { // 去重操作continue;
}那我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据当遍历到第一个-1 的时候判断 下一个也是-1那这组数据就pass了。
我们要做的是 不能有重复的三元组但三元组内的元素是可以重复的
所以这里是有两个重复的维度。
那么应该这么写
if (i 0 nums[i] nums[i - 1]) {continue;
}这么写就是当前使用 nums[i]我们判断前一位是不是一样的元素在看 {-1, -1 ,2} 这组数据当遍历到 第一个 -1 的时候只要前一位没有-1那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。
这是一个非常细节的思考过程。
b与c的去重
很多人写本题的时候去重的逻辑多加了 对right 和left 的去重代码中注释部分
while (right left) {if (nums[i] nums[left] nums[right] 0) {right--;// 去重 rightwhile (left right nums[right] nums[right 1]) right--;} else if (nums[i] nums[left] nums[right] 0) {left;// 去重 leftwhile (left right nums[left] nums[left - 1]) left;} else {}
}但细想一下这种去重其实对提升程序运行效率是没有帮助的。
拿right去重为例即使不加这个去重逻辑依然根据 while (right left) 和 if (nums[i] nums[left] nums[right] 0) 去完成right-- 的操作。
多加了 while (left right nums[right] nums[right 1]) right--; 这一行代码其实就是把 需要执行的逻辑提前执行了但并没有减少 判断的逻辑。
最直白的思考过程就是right还是一个数一个数的减下去的所以在哪里减的都是一样的。
所以这种去重 是可以不加的。 仅仅是 把去重的逻辑提前了而已。
