3sum

这道题目和3sum closest差不多，都是用夹逼法可以做到，时间复杂度是max(O(n^log n), O(n^2)) 但是需要注意的是这道题目要求得到的结果不重复，不重复的结果需要用unique去掉重复的那些元素 unique是C++中用来除去容器中相同元素的函数，它的做法是将重复的元素用后面的元素进行覆盖，所以原来容器的大小是不变化的，在unique后面接一个erase就能够去掉重复元素了 其实用记录上一个结果的方式也能够去掉重复，代码如下 class Solution { public: vector > threeSum(vector &num) { vector> result; sort(num.begin(), num.end()); if (num.size() <= 2) return result; const int target = 0; int prev_a, prev_b, prev_c; for (auto a = num.begin(); a != prev(num.end(), 2); prev_a = *a, a++){ if (a != num.begin() && prev_a == *a) continue ; auto b = next(a); auto c = prev(num.end()); prev_b = *b + 1; prev_c = *c + 1; while (b < c){ int cur_sum = *a + *b + *c; if (cur_sum == target){ if (!(prev_b == *b && prev_c == *c)){ result.push_back({*a, *b, *c}); prev_b = *b, prev_c = *c; } b++, c--; continue ; } if (cur_sum > target) c--; else b++; } } //sort(result.begin(), result.end()); //result.erase(unique(result.begin(), result.end()), result.end()); return result; } };