口碑营销网站,电子商务平台如何推广营销,查询网址域名ip地址,公司官网用wordpress题目链接
力扣15.三数之和 题目描述
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意#xff1a;答…题目链接
力扣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] 105 思路分析
知识点双指针、碰撞指针、排序
解析
首先我们对于给定数组先进行排序然后再使用双指针算法进行实现。
具体步骤
1.先进行排序。
2.从第一个数开始进行固定当前位置为i定义左右两个指针left,rightleft每次从i的下一个位置开始而right每次都从最右边开始。
3.每次求出left和right所指向的数的和看看这个和是否等于i位置的倒数如果大right--如果小left直到找到匹配的数后将结果存放到返回数组里此时left和right--同时进行。
4.为了避免出现重复结果我们之前已经对数组进行了排序假设此时left和right指向的值的和满足条件又因为排序后连续的数会放到一起所以left后面和right前面就会存在重复元素此时我们需要跳过它同时也要避免leftright因为前面匹配后lefti已经移动了一次如果用left后面的值当作判断的话可能left的下一个元素是新元素而此时left还在重复元素上所以要有left前面的值进行判断right也是一样反过来就行。
5.匹配完后i就要继续向下移动而i也会存在重复元素的问题也要记得查重。
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;//用于存储返回值sort(nums.begin(),nums.end());int nnums.size();int i0;while(in){if(nums[i]0) break;//小优化因为i位置大于0的话后面不可能有数相加等于它int lefti1,rightn-1,target-nums[i];while(leftright){int sumnums[left]nums[right];if(sumtarget) right--;else if(sumtarget) left;else{ret.push_back({nums[left],nums[right],nums[i]});left;right--;while(leftrightnums[left]nums[left-1]) left;while(leftrightnums[right]nums[right1]) right--;}}i;while(innums[i]nums[i-1]) i;}return ret;}
};
