15. 三数之和

15. 三数之和 - 力扣（LeetCode）

class Solution {
public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> Result;
    std::sort(nums.begin(), nums.end());
    int Size = nums.size();

    for (int A = 0; A < Size; ++A) {
      // Skip to a different number.
      if (A > 0 && nums[A] == nums[A - 1])
        continue;

      int C = Size - 1;
      // A + B + C == 0 => B + C == -A.
      int Complementary = -nums[A];
      // In each loop, the total step of B and C won't exceed Size.
      for (int B = A + 1; B < Size; ++B) {
        // Skip to a different number.
        if (B > A + 1 && nums[B] == nums[B - 1])
          continue;

        // Since the array has been sorted, C > B is ensured. So, any time when
        // B + C > -A, C should move left by one step, as we need left hand side
        // to be smaller than current value. At this moment, B won't move. You
        // can see how B and C are tied together.
        while (B < C && nums[B] + nums[C] > Complementary)
          --C;

        // Any value of C won't help us achieve B + C == -A.
        if (B == C)
          break;

        if (nums[B] + nums[C] == Complementary)
          Result.push_back({nums[A], nums[B], nums[C]});
      }
    }
    return Result;
  }
};

上面这个是照着官方题解写出来的。要注意的是，官解的做法是在两层循环中分别固定 A、B，然后让 C 自由移动。实际上如果写 while (B < C) {} 的双指针的话也是非常自然的，同样是先定序、再比较、然后移动的思路。二刷的时候注意一下。

二刷

class Solution {
public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    int N = nums.size();
    vector<vector<int>> Result;
    // First, make it ordered.
    sort(nums.begin(), nums.end());

    for (int i = 0; i < N; ++i) {
      // Advancement.
      if (i != 0 && nums[i] == nums[i - 1])
        continue;
      // j moves forward, k moves backward.
      int j = i + 1, k = N - 1;
      while (j < k) {
        int Sum = nums[i] + nums[j] + nums[k];
        if (Sum == 0) {
          Result.push_back({nums[i], nums[j], nums[k]});
          // We need to move BOTH i and j, since the vector is ordered, and it
          // is guaranteed that every time only one of the pointers is changed,
          // the sum is not 0 anymore.
          while (++j < k && nums[j] == nums[j - 1]) {}
          while (j < --k && nums[k] == nums[k + 1]) {}
        } else if (Sum < 0) {
          while (++j < k && nums[j] == nums[j - 1]) {}
        } else {
          while (j < --k && nums[k] == nums[k + 1]) {}
        }
      }
    }
    return Result;
  }
};

这种双指针法更清晰、容易记忆，并且逻辑通顺，用 for 和 while 两种循环区分了外层的 \(i\) 和内层的 \(j,k\)。如果想要整体更整齐，也可以直接把最外层改为 while (i < N)，并且把单行循环代表的 advance 操作放至循环最后，也即

while (i < N) {
  // Compare first...
  while (++i < N && nums[j] == nums[j - 1]) {}
}

这两种方法都是非常容易记忆的。

三刷

class Solution {
public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    std::set<vector<int>> Triples;
    for (int i = 0; i < nums.size() - 2; ++i) {
      int j = i + 1, k = nums.size() - 1;
      while (j != k) {
        int Sum = nums[i] + nums[j] + nums[k];
        if (Sum == 0) {
          Triples.insert({nums[i], nums[j], nums[k]});
          ++j;
        }
        if (j != k && Sum < 0)
          ++j;
        if (j != k && Sum > 0)
          --k;
      }
    }
    return vector<vector<int>>(Triples.begin(), Triples.end());
  }
};

这个写法确实是\(\mathrm O\left(n^2\right)\)的，但实际上std::set在输入规模比较大的情况下还是占用了很大一部分的时间和空间。实际上，我们需要在步进指针的时候，如果采用快进的办法，也就是直接跳过已经被统计过的元素，这样就实现了天然的去重。

class Solution {
public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> Result;
    std::sort(nums.begin(), nums.end());

    int i = 0;
    int IVal = nums[i];
    while (i != nums.size() - 1) {
      int j = i + 1, k = nums.size() - 1;
      int JVal = nums[j], KVal = nums[k];
      while (j != k) {
        int Sum = IVal + JVal + KVal;
        if (Sum == 0) {
          Result.push_back({IVal, JVal, KVal});
          // Advance j, k
          while (j != k && nums[j] == JVal) ++j;
          JVal = nums[j];
          while (j != k && nums[k] == KVal) --k;
          KVal = nums[k];
        } else if (Sum < 0) {
          // Advance j
          while (j != k && nums[j] == JVal) ++j;
          JVal = nums[j];
        } else {
          // Advance k
          while (j != k && nums[k] == KVal) --k;
          KVal = nums[k];
        }
      }
      // Advance i
      while (i != nums.size() - 1 && nums[i] == IVal) ++i;
      IVal = nums[i];
    }

    return Result;
  }
};

我这里的快进并没有像二刷那样写成

while (++j < k && nums[j] == nums[j - 1]);

的形式，是因为这样做会不可避免地需要考虑自增的副作用所导致的不共时性，进而不得不在边界条件的判断当中引入偏序关系。虽然按理来说二刷那种写法的常数确实要小一丢丢。

注意快进最好是在判断之后再快进。其实二刷里那个写在外层循环开头的快进有点问题的，你也可以发现它不得不增加了一个i != 0的条件。