网站ipc备案,方法网站目录,京津冀协同发展,南京做网站哪家公司最好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
整体思路 本题最重要的就是避免超时也就是去重疯狂去重 题干表明顺序并不重要那我们只要找到和为0的三个数就行对数组元素排序排好序对于找符合题干的元素就很容易了就面对了第二大问题去重 比如第一个例子排好序为-4-1-1012 当我们遍历这个数组的时候-1和-1是相同的也就是对应的答案是相同的那么只考虑一个就可以 找符合相加0利用双指针遍历指针1在当前i的下一个指针2在最后一个元素 如果找到了相加等于0输出这组元素并且去重之后再让两个指针同时向中间移动再看有没有符合条件的直到1、2指针重合证明全遍历完了结束当前i到下一个i1 如果没找到相加等于0的和0对比大于0的证明数太大2指针向左移动排序后左小右大 小于0的证明数太小1指针向右移动
代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ans;sort(nums.begin(), nums.end()); // 先对数组进行排序for (int i 0; i nums.size() - 2; i) {if (i 0 nums[i] nums[i - 1]) continue; // 跳过重复的元素int left i 1, right nums.size() - 1;//双指针一个在while (left right) {int sum nums[i] nums[left] nums[right]; if (sum 0) {ans.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--;left;right--;} else if (sum 0) {left;} else {right--;}}}return ans;}
};
