LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 将数组排序，遍历每个元素，每次遍历时，在右侧找出两个元素即可

-4 -1 -1 0 1 2

-4 => 和为 4 的元素 => 不存在
-1 => 和为 1 的元素 => [-1, 2], [0, 1] => [-1, -1, 2], [-1, 0, 1]
-1 => 和为 1 的元素 => [0, 1] => [-1, 0, 1]
0  => 和为 0 的元素 => 不存在
1  => 和为 -1 的元素 => 不存在
2  => 和为 -2 的元素 => 不存在

• 将右侧视为一个窗口，初始化 l 和 r 为左右边界。如果两者和超出目标值，则和要缩小，左移 r 即可。如果小于目标值，则和要扩大，右移 l 即可。如果恰好等于目标值，记录到结果中，再同时右移 l 和左移 r，因为不能包含重复解，因此应持续移动直到元素与上次记录到结果中的不同

-4 -1 -1 0 1 2
 |  |  | | | |
 0  1  2 3 4 5

i = 0 nums[i] = 4 => 找出和为 4 的元素：
l = 1 r = 5 => -1 + 2 < 4 => 右移 l
l = 2 r = 5 => -1 + 2 < 4 => 右移 l
l = 3 r = 5 => 0 + 2 < 4 => 右移 l
l = 4 r = 5 => 1 + 2 < 4 => 右移 l
l = 5 r = 5 => 不满足 l < r，查找下一个 i

i = 1 nums[i] = -1 => 找出和为 1 的元素：
l = 2 r = 5 => -1 + 2 == 1 => 满足条件，添加 [-1, -1, 2] 到结果，再右移 l和左移 r
l = 3 r = 4 => 0 + 1 == 1 => 满足条件，添加 [-1, 0, 1] 到结果，再右移 l 和左移 r
l = 4 r = 3 => 不满足l < r，查找下一个 i

i = 2 nums[i] = -1 => 与 nums[i - 1] 重复，不会有不重复解，查找下一个 i

i = 3 nums[3] = 0 => 找出和为 0 的元素：
l = 4 r = 5 => 1 + 2 > 0 => 左移r => 左移后不满足 l < r，查找下一个 i

i = 4 => 右侧只有一个元素，一定无解，跳出循环，查找结束 

• 解法如下

class Solution {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    int sz = size(nums);
    if (sz < 3) return res;
    sort(begin(nums), end(nums));
    for (int i = 0; i < sz - 2; ++i) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }
      int l = i + 1;
      int r = sz - 1;
      int target = -nums[i];
      while (l < r) {
        if (nums[l] + nums[r] == target) {
          while (l < r && nums[l] == nums[l + 1]) {
            ++l;
          }
          while (l < r && nums[r] == nums[r - 1]) {
            --r;
          }
          res.emplace_back(vector<int>{nums[i], nums[l], nums[r]});
          ++l;
          --r;
        } else if (nums[l] + nums[r] > target) {
          --r;
        } else {
          ++l;
        }
      }
    }
    return res;
  }
};