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: 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]
]
关于这个问题，我最初的想法很简单，就是暴力搜索所有数值，然后得到所有的和为0的子序列。但是这个做法的问题是会得到重复的序列,那么思考下去就是，判断得到的子序列是否与前面已经存下来的数据重复，如果重复则不存。
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > threeSum(vector<int>& nums);
bool compare(vector<int> &v1, vector<int>& v2);
vector<vector<int> > threeSum(vector<int>& nums) {
vector< vector<int> >ret;
if (nums.size() < 3) {
return ret;
}
int size = nums.size();
for (vector<int>::const_iterator it = nums.cbegin(); it != (nums.cend() - 2); it++) {
int first = *it;
for (vector<int>::const_iterator it2 = it + 1; it2 != (nums.end() - 1); it2++) {
int second = *it2;
for (vector<int>::const_iterator it3 = it2 + 1; it3 != nums.end(); it3++) {
if (*it3 + second + first) {
continue;
} else {
vector<int> tmp;
tmp.push_back(first);
tmp.push_back(second);
tmp.push_back(*it3);
bool dump = false;
for (vector<vector<int> >::iterator itt = ret.begin(); itt != ret.end(); itt++) {
if (compare(tmp, *itt)) {
dump = true;
break;
}
}
if (dump) {
continue;
}
ret.push_back(tmp);
cout<< *it3 << second << first <<endl;
}
}
}
}
return ret;
}
bool compare(vector<int> &v1, vector<int>& v2) {
for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
bool ret = false;
for (vector<int>::iterator it2 = v2.begin(); it2 != v2.end(); it2++) {
if (*it == *it2) {
// cout<<*it2<<endl;
v2.erase(it2);
// cout<<*it2<<endl;
ret = true;
break;
}
}
if (!ret) {
return false;
}
}
return true;
}
这一坨玩意儿实际上是可行的，但是运行超时了，时间复杂度>O(n^5) 基本就是一坨垃圾了。
考虑新的计算方法，在计算中就规避掉会导致重复的情况。经过思考，重复的序列和重复的数字是有关系的，即当已经使用过某一个数字，来搜索剩余两个数字，如果后面这个数字再次出现，那么就不必要再搜索一次了，搜索的结果就是重复的结果，是无意义的。
为了使计算方便，首先做个排序，然后依次判断，如果重复出现就不再计算，这样下来时间复杂度降到了O(n^3)
Runtime: 139 ms
Your runtime beats 1.36% of cpp submissions.
还是很可怜的成绩，需要继续优化。
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > threeSum(vector<int>& nums);
void sortv(vector<int> &vec);
vector<vector<int> > threeSum(vector<int>& nums) {
vector< vector<int> >ret;
if (nums.size() < 2) {
return ret;
}
if (nums.size() == 3) {
if (nums[1] + nums[2] + nums[0] == 0) {
ret.push_back(nums);
}
return ret;
}
sortv(nums);
int size = nums.size();
int last_1;
int last_2;
int last_3;
for (vector<int>::const_iterator it = nums.cbegin(); it != (nums.cend() - 2); it++) {
int first = *it;
// cout<<"first and last_1"<<first<<last_1<<endl;
if (it != nums.cbegin()) {
if (first == last_1) {
// cout<<"same first"<<first<<endl;
continue;
}
}
last_1 = first;
// 2rd Loop
for (vector<int>::const_iterator it2 = it + 1; it2 != (nums.end() - 1); it2++) {
int second = *it2;
// cout<<"No.2 for loop: "<<(*it2)<<" last2: "<<last_2<<endl;
if (it2 != it + 1) {
if (second == last_2) {
// cout<<"same second"<<second<<endl;
continue;
}
}
last_2 = second;
// Third loop
for (vector<int>::const_iterator it3 = it2 + 1; it3 != nums.end(); it3++) {
int third = *it3;
if (it3 != it2 + 1) {
if (third == last_3) {
// cout<<"same third"<<third<<endl;
continue;
}
}
last_3 = third;
if (*it3 + second + first) {
continue;
} else {
vector<int> tmp;
tmp.push_back(first);
tmp.push_back(second);
tmp.push_back(*it3);
ret.push_back(tmp);
// cout<< *it3 << second << first <<endl;
}
}
}
}
return ret;
}
void sortv(vector<int> &vec) {
for (int i = vec.size(); i > 0; --i) {
for (int j = 0; j < i - 1; ++j) {
if (vec[j] > vec[j + 1]) {
int t = vec[j];
vec[j] = vec[j + 1];
vec[j + 1] = t;
}
}
}
// for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
// cout<<"Sort:"<<(*it)<<endl;
// }
}
果然自己脑子还是不够用，上网查了一下人家的解法，复杂度直接降到O(n^2).具体代码可见： 九章 - 3Sum 人家如何减少一个量级的复杂度呢？将数组排序以后，首先一个完整的循环,nums[i],那么我们需要的另两个数的和就应该是 -nums[i]. 现在有两个游标，一个从头，一个从尾。因为无论如何不可能三个数值都为正或者都负，肯定是一个更靠近头部，一个更靠近尾部。如果求得的和比我们要的小，说明起点太小，往前面挪一个，反则往后挪。主要在搜寻中遇到重复的数据也一样把他去除掉。
class Solution {
public:
/**
* @param numbers : Give an array numbers of n integer
* @return : Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int> > threeSum(vector<int> &nums) {
vector<vector<int> > result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// two sum;
int start = i + 1, end = nums.size() - 1;
int target = -nums[i];
while (start < end) {
if (start > i + 1 && nums[start - 1] == nums[start]) {
start++;
continue;
}
if (nums[start] + nums[end] < target) {
start++;
} else if (nums[start] + nums[end] > target) {
end--;
} else {
vector<int> triple;
triple.push_back(nums[i]);
triple.push_back(nums[start]);
triple.push_back(nums[end]);
result.push_back(triple);
start++;
}
}
}
return result;
}
};