Skip to content

Instantly share code, notes, and snippets.

@soulmachine
Created October 4, 2013 16:04
Show Gist options
  • Save soulmachine/6828381 to your computer and use it in GitHub Desktop.
Save soulmachine/6828381 to your computer and use it in GitHub Desktop.
LeetCode 4Sum, TLE,怎么破?
// LeetCode, 4Sum
// 先排序,然后二分查找
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& num, int target) {
vector<vector<int>> result;
if (num.size() < 4) return result;
sort(num.begin(), num.end());
auto last = num.end();
for (auto a = num.begin(); a < prev(last, 3);
a = upper_bound(a, prev(last, 3), *a)) {
for (auto b = next(a); b < prev(last, 2);
b = upper_bound(b, prev(last, 2), *b)) {
for (auto c = next(b); c < prev(last);
c = upper_bound(c, prev(last), *c)) {
const int d = target - *a - *b - *c;
if (binary_search(next(c), last, d))
result.push_back(vector<int> { *a, *b, *c, d });
}
}
}
return result;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment