网站建设新闻咨询,中国建筑第八工程局招聘信息,服装网站建设与实现,js 上传wordpress目录
力扣15. 三数之和
解析代码 力扣15. 三数之和
难度 中等
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三…目录
力扣15. 三数之和
解析代码 力扣15. 三数之和
难度 中等
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。示例 2
输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例 3
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。提示
3 nums.length 3000-105 nums[i] 10^5
class Solution {
public:vectorvectorint threeSum(vectorint nums) {}
}; 解析代码
建议看了上一篇双指针⑥剑指 Offer 57. 和为s的两个数字再来看这一题。 与两数之和稍微不同的是题目中要求找到所有「不重复」 的三元组。那我们可以利用在两数之和那里用的双指针思想来对我们的暴力枚举做优化先排序然后固定- -个数a在这个数后面的区间内使用「双指针算法」快速找到两个数之和等于-a即可。但是要注意的是这道题里面需要有「去重」操作找到一个结果之后left和right | 指针要「跳过重复」 的元素当使用完一-次双指针算法之后固定的a也要「跳过重复」的元素。 class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;sort(nums.begin(), nums.end());int n nums.size();for(int i 0; i n;) // i是固定的数的下标{if(nums[i] 0) // 小优化{break;}int left i 1, right n - 1, target -nums[i];while(left right){int sum nums[left] nums[right];if(sum target){left;}else if(sum target){--right;}else{ret.push_back({nums[i], nums[left], nums[right--]});while(left right nums[left] nums[left - 1]) // 去重{left;}while(left right nums[right] nums[right 1]){--right;}}}i;while(i n nums[i] nums[i - 1]) // 对i去重-for循环里不用i了{i;}}return ret;}
};
