class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
std::sort(num.begin(), num.end());
int n = num.size();
vector<vector<int> > result;
if(n < 3){
return result;
}
for(int i = n - 1; i >= 1; i--) {
if(i < n - 1 &&num[i] ==num[i+1]) { // didn't have this previously, so Output Limit Exceed
continue;
}
int target = -num[i];
vector<vector<int> > temp(twoSum(num, 0, i - 1, target));
for(auto& item : temp) {
item.emplace_back(num[i]);
result.emplace_back(item);
}
}
return result;
}
vector<vector<int> > twoSum(const vector<int>& num, int start, int end, int target) {
vector<vector<int> > result;
while(start < end) {
int sum = num[start] + num[end];
if (sum > target) {
while(num[end] == num[--end]);
} else if (sum == target) {
vector<int> found{num[start], num[end]};
result.emplace_back(found);
while(num[end] == num[--end]);
while(num[start] == num[++start]);
} else {
while(num[start] == num[++start]);
}
}
return result;
}
};
4/02/2014
Leetcode -- 3Sum
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment