class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
auto two_sum = set<int>();
int best = nums[0]+nums[1]+nums[2];
for (int i = 0; i < nums.size(); i++) {
auto it = two_sum.upper_bound(targetnums[i]);
if (it != two_sum.end()) {
int candidate = nums[i] + *it;
if (abs(candidatetarget) < abs(besttarget)) {
best = candidate;
}
}
if (it != two_sum.begin()) {
it;
int candidate = nums[i] + *it;
if (abs(candidatetarget) < abs(besttarget)) {
best = candidate;
}
}
for (int j = 0; j < i; j++) {
two_sum.insert(nums[i]+nums[j]);
}
}
return best;
}
};
Why does my O(n^2) algorithm get TLE?


I can't tell you why for sure, but I can tell you how to fix it.
Add an optimization to return once you've found an answer that can't be beat. I'm running a O(n^3) algorithm with a for(for(for))) loop, but with the little heuristic I described it passes.
I'm intentionally being a bit cryptic here so as not to give it away too blatantly. If you want me to come right out and tell you what I'm talking about just let me know.