[cpp]
class Solution {
public:
vector > fourSum(vector &num, int target) {
vector > ret;
if(num.size() < 4) return ret;
sort(num.begin(), num.end());
for(int i = 0; i < num.size(); ++i)
for(int j = i + 1; j < num.size(); ++j) {
int left = j + 1;
int right = (int)num.size() - 1;
int sum = 0;
while(left < right){
sum=num[i]+num[j]+num[left]+num[right];
if(target == sum){
ret.push_back(vector(4));
ret.back()[0]=num[i];
ret.back()[1]=num[j];
ret.back()[2]=num[left];
ret.back()[3]=num[right];
++left;
--right;
}
else if(sum > target)
--right;
else
++left;
}
}
vector>:: iterator it = unique(ret.begin(),ret.end());
ret.resize(distance(ret.begin(), it));
return ret;
}
};
The function unique Removes all but the first element from every consecutive group of equivalent elements in the range [first,last). Here's the example from the cplusplus.com. Vectors could be sorted since we could compare every two vectors.
[cpp]
// unique algorithm example
#include // std::cout
#include // std::unique, std::distance
#include // std::vector
bool myfunction (int i, int j) {
return (i==j);
}
int main () {
int myints[] = {10,20,20,20,30,30,20,20,10}; // 10 20 20 20 30 30 20 20 10
std::vector myvector (myints,myints+9);
// using default comparison:
std::vector::iterator it;
it = std::unique (myvector.begin(), myvector.end()); // 10 20 30 20 10
// ^
myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30 20 10
// using predicate comparison:
std::unique (myvector.begin(), myvector.end(), myfunction); // (no changes)
// print out content:
std::cout << "myvector contains:";
for (it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Another way to avoid duplicates is using set, int num; string tmp += num; So num could be treated as a character. However, when num > 255, it could be seen as num%256. So,
[cpp]
#include
#include
#include
#include
#include
#include
#include//不添加string会出现模版的错误
using namespace std;
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int nSize = num.size();
vector< vector > result;
if (nSize < 4) return result;
sort(num.begin(), num.end());
vector mid(4);//指定对象的大小为4，mid(4,1)含有4个元素，每个为1
set isExit;
for (int i = 0; i < nSize - 3; ++i)
{
mid[0] = num[i];
for (int j = i + 1; j < nSize - 2; ++j)
{
mid[1] = num[j];
int l = j + 1;
int r = nSize - 1;
int sum = target - num[i] - num[j];
while(l < r)
{
int tmp = num[l] + num[r];
if (sum == tmp)
{
string str;
str += num[