三数之和

这道题要不重不漏地找出数组中三数相加等于零的所有三元组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
      // 跳过相同的数
      if (i && nums[i] == nums[i - 1]) continue;
      for (int j = i + 1, k = nums.size() - 1; j < k; j++) {
        // 跳过相同的数
        if (j > i + 1 && nums[j] == nums[j - 1]) continue;
        // 只要三个数相加大于 0，k--
        while (j < k - 1 && nums[i] + nums[j] + nums[k] > 0) k--;
        // 检查是不是 0
        if (nums[i] + nums[j] + nums[k] == 0) {
          res.push_back({nums[i], nums[j], nums[k]});
        }
      }
    }
    return res;
  }
};