leetcode 4Sum Summary for unique and duplicates(二)
i];
str += num[j];
str += num[l];
str += num[r];
set::iterator itr = isExit.find(str);//利用set标记是否被占用
if (itr == isExit.end())
{
isExit.insert(str);
mid[2] = num[l];
mid[3] = num[r];
result.push_back(mid);
}
++l;
--r;
}
else if(sum > tmp)
++l;
else
--r;
}
}
}
return result;
}
};
int main(){
Solution s;
int a[4] = {4,5,6,7};
vector > res;
vector vec(a, a + 4);
res=s.fourSum(vec,26);
return 0;
}
The last way is to use direct comparison.
[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) {
if (i > 0 && num[i] == num[i - 1])
continue;
for(int j = i + 1; j < num.size(); ++j) {
if (j > i + 1 && num[j] == num[j - 1])
continue;
int left = j + 1;
int right = (int)num.size() - 1;
int sum = 0;
while(left < right){
if (left > j + 1 && num[left] == num[left - 1]) {
++left;
continue;
}
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;
}
}
}
return ret;
}
};