先排序,然后以第一个值为基准开始遍历,用双指针求第二个值和第三个值。
class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { sort(num.begin(), num.end()); vector<vector<int> > res; if (num.size() < 3) return res; for (int i = 0; i < num.size() - 2; ++i) { int j = i + 1; int k = num.size() - 1; int target = -num[i]; while (j < k) { if (num[j] + num[k] > target) --k; else if (num[j] + num[k] < target) ++j; else { vector<int> current = {num[i], num[j], num[k]}; res.push_back(current); while (j + 1 < k && num[j+1] == num[j]) ++j; // 防止重复 while (k - 1 > j && num[k-1] == num[k]) --k; // 防止重复 ++j; --k; } } while (i + 1 < num.size() - 2 && num[i+1] == num[i]) ++i; // 防止重复 } return res; } };