响应式 网站建设,wordpress 小工具调用,河北省建设工程质监站网站,排名好的徐州网站开发三数之和
力扣题目链接(opens new window)
给你一个包含 n 个整数的数组 nums#xff0c;判断 nums 中是否存在三个元素 a#xff0c;b#xff0c;c #xff0c;使得 a b c 0 #xff1f;请你找出所有满足条件且不重复的三元组。
注意#xff1a; 答案中不可以包含…三数之和
力扣题目链接(opens new window)
给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 请你找出所有满足条件且不重复的三元组。
注意 答案中不可以包含重复的三元组。
示例
给定数组 nums [-1, 0, 1, 2, -1, -4]
满足要求的三元组集合为 [ [-1, 0, 1], [-1, -1, 2] ]
思路
这道题可以说是噩梦的开始我们的平常思路是通过哈希表用三层循环寻找符合要求的解同时每一层循环都要进行一次去重繁琐无比。
可以使用双指针法求解。
思路如下
首先对数组进行一个从小到大排序。
定义三个指针
cur按顺序指向当前位置left初始位置为cur的洗一个位置right初始位置为数组最末尾位置
由于事先排序过因此当cur指针所指数值大于0时直接返回res。要求三数之和0
这里要对cur进行一个去重。
去重思路当cur与cur-1的值相等时说明已经用过了因此直接continue。
代码为if(nums[cur] nums[cur -1 ])return res;
为什么这里是cur-1而不是1呢举个例子就可以理解由于我们left是在cur的后一位如果与1比较则是与left比较这部分的意义便成为判断三数里的两个数是否相等。这不符合我们的要求。因此我们应该去前一位由于cur从0开始我们应该再加一个判断条件if(cur 0 nums[cur] nums[cur -1 ])return res;
left、right寻找目标值
循环条件为while(left right)为何不能加上等于号加上等于号就变成两个数了不符合要求。
我们在循环里做了两件事
第一件是判断当前三数之和是否大于0/小于0/等于0若大于0则right–小于同理指针往后移动一位。
若是0
这里意味着找到了一组答案将其收进res数组。
接下来对letf、right进行去重。
代码如下
while(left right nums[right] nums[right - 1])right--;
while(left right nums[left] nums[left 1])left;原理如上最后记得再往前一位。
代码如下
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());int left,right;vectorvectorint res;for(int i 0;inums.size();i){if(nums[i] 0)return res;if(i 0 nums[i] nums[i-1])continue;left i1;right nums.size()-1;while(left right){if(nums[i] nums[left] nums[right] 0)right--;else if(nums[i] nums[left] nums[right] 0)left;else{res.push_back(vectorint{nums[i],nums[left],nums[right]});while(left right nums[left] nums[left1])left;while(left right nums[right] nums[right-1])right--;// 双指针收束left;right--;}} }return res;}
};
