给公司建网站 深圳,唐山 网站建设,做网站360业务,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 。题目解释
在数组中找到三个元素,然后让他们的和为0,注意的是我们结果不要重复.
算法原理
这个很简单,我们先排序.然后固定一个元素val,在这个前面寻找两个元素,求他们的和为-val.这不就退化成我们的两个元素之和了吗.这里我们需要解决两个问题
为何当val为最大值的时候,我们在前面选两个数一定是所有情况,这是对于每一个结果而言,我们的三个元素中一定存在一个值比较大(都为0的也是符合下面的), 我们将数组中的每一个元素都作为一个最大值,让后遍历整个数组,就可以收取所有情况如何解决重复问题,这里提供两个方法,一个是都保存下来,等到最后处理,麻烦.第二个是在收集结果的时候就处理了
细节补充
补充下细节,我们如何处理.
固定下最大值val, 收集结果之后跳过重复的val对于收集的一次结果,跳过重复的num[left]和num[right]
代码编写
class Solution
{
public:vectorvectorint threeSum(vectorint nums){vectorvectorint reuslt;sort(nums.begin(), nums.end());for (int i nums.size() - 1; i 2;){int val nums[i];int left 0;int right i - 1;while (left right){int sum nums[left] nums[right];if (sum val 0){// 收集reuslt.push_back({nums[left], nums[right], val});// 跟新left;right--;while (left right nums[left] nums[left - 1])left;while (left right nums[right] nums[right 1])right--;}else if (sum -val){right--;}else{left;}}while (i 2 nums[i] val){i--;}}return reuslt;}
};
