首页 > 代码库 > [C++]LeetCode: 70 3Sum
[C++]LeetCode: 70 3Sum
题目:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: (-1, 0, 1) (-1, -1, 2)
思路:
本题的解法类似于LeetCode: 15 3Sum Closest (plus JAVA Code).也是使用先排序,后夹逼的方法求解答案。
不同的地方在于,我们需要根据第一个元素的移动(改变),不断确定新的target, 即twosum.
同时我们需要考虑如何跳过重复的集合,移动夹逼的两个左右指针时,需要进行判断移动前后元素是否相等,重复则skip。
Attention:
1. 为了不改变原来的数组,我将数组存在ivec中,再进行排序和后续操作。
//不想改变原数组,所以存在ivec中 vector<int> ivec(num.begin(), num.end()); if(num.size() < 3) return ret; sort(ivec.begin(), ivec.end());2. 在外层大的循环下,我们不设置i++, 在循环体内判断,如果有重复数字,不断跳过。
for(int i = 0; i < ivec.size() - 2; )
//如果之间有重复的,就一直跳过 do{ i++; }while(i < ivec.size() - 1 && ivec[i-1] == ivec[i]);3. 进行循环后,每次都需要计算 num[i]的相反数,作为target来匹配。可能存在多个匹配情况,所以即使一次匹配成功,仍然需要改变夹逼指针j 和 k,寻找其他可能的匹配组合。
int twosum = 0 - ivec[i]; //把-num[i]作为target去寻找匹配的两个数 while(j < k) { //即使找到第一个匹配的项,仍然需要移动坐标,寻找其他可能匹配数 if(ivec[j] + ivec[k] == twosum) { vector<int> tmp{ivec[i], ivec[j], ivec[k]}; ret.push_back(tmp); do{ j++; }while(j < k && ivec[j] == ivec[j-1]); do{ k--; }while(j < k && ivec[k] == ivec[k+1]); }复杂度: O(N^2)
AC Code:
class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int>> ret; //不想改变原数组,所以存在ivec中 vector<int> ivec(num.begin(), num.end()); if(num.size() < 3) return ret; sort(ivec.begin(), ivec.end()); for(int i = 0; i < ivec.size() - 2; ) { int j = i + 1; int k = ivec.size() - 1; int twosum = 0 - ivec[i]; //把-num[i]作为target去寻找匹配的两个数 while(j < k) { //即使找到第一个匹配的项,仍然需要移动坐标,寻找其他可能匹配数 if(ivec[j] + ivec[k] == twosum) { vector<int> tmp{ivec[i], ivec[j], ivec[k]}; ret.push_back(tmp); do{ j++; }while(j < k && ivec[j] == ivec[j-1]); do{ k--; }while(j < k && ivec[k] == ivec[k+1]); } else if(ivec[j] + ivec[k] < twosum) j++; else k--; } //如果之间有重复的,就一直跳过 do{ i++; }while(i < ivec.size() - 1 && ivec[i-1] == ivec[i]); } return ret; } };
这道题其实还可以嵌套一个twosum子程序来做。其他博文中有给出。3Sum
重点是,我们一定要注意细节的处理,就是夹逼指针的移动。
[C++]LeetCode: 70 3Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。