leetcode:3Sum
来源：程序员人生 发布时间：2015-01-09 08:38:46 阅读次数：2476次
1、 题目
给出1个数组S包括n个整数，找出不重复的3个元素a、b、c使a+b+c=0。
例如给出S = {⑴0 1 2 ⑴ ⑷},
结果是:
(⑴, 0, 1)
(⑴, ⑴, 2)
2、 分析
首先我们看到这个题目会想到Brute-Force(简单的模式匹配)直接使用3重循环来匹配所有元素组合找出结果。虽然我在每层循环都做了优化来减少1些遍历，但是依然不能在数量级上减少，所以总是超时。
Brute-Force(简单的模式匹配)超时期码：
//超时
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
int len = num.size();
int res;
vector<vector<int>> ans;
if(len<=2) return ans;
for(int i=0;i<len⑵;i++){
for(int j=i+1;j<len⑴;j++){
res = 0-num[i]-num[j];
for(int k=j+1;j<len;j++){
if(num[k] == res){
vector<int> ves;
ves.push_back(num[i]);
ves.push_back(num[j]);
ves.push_back(num[k]);
ans.push_back(ves);
}
}
}
}
return ans;
}
};
所以我们要换个思路，1般情况下对数组的查询我们为了方便总是希望它是有序的，因此第1步应当要将数组排序，那末接下来我们就将当前的节点作为第1个元素，那末接下来就是寻觅剩下的两个元素，由于它已是有序的了，所以可使用左右指针法，设置左右指针夹逼，总的时间复杂度为O(n^2+nlogn)=(n^2),空间复杂度是O(n)
但注意为了不重复，对排序后的数组，当我们枚举第1个数时，如果遇到重复的就直接跳过，这1点其实很重要，我没有写的时候1会超时；还有1点当我们找到1个符合的2元组（第2个数和第3个数）时，也分别对第2个数和第3个数去重。可以看出这道题细节处理是不是到位决定了能否通过。
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
int len = num.size();
//中间结果、左指针、右指针
int res,left,right;
vector<vector<int>> ans;
if(len<=2) return ans;
//将数组排序
sort(num.begin(), num.end());
for(int i=0;i<len⑵;i++){
//将重复的疏忽，ps：刚开始没有关心这1点,总是超时，加上后秒过，汗...
while(i > 0 && i < len - 2 && num[i] == num[i - 1])
++i;
res = -num[i];
left = i+1;
right = len ⑴;
while(left<right){
//寻觅符合元素
if(num[left] + num[right] < res){
left++;
}
else if(num[left] + num[right] > res){
right--;
}
else {
//将结果放入ans
vector<int> ves;
ves.push_back(num[i]);
ves.push_back(num[left]);
ves.push_back(num[right]);
ans.push_back(ves);
//解决重复问题
left++;
while(left < right && num[left] == num[left⑴])
left++;
right--;
while(left < right && num[right] == num[right+1])
right--;
}
}
}
return ans;
}
};
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
