[LeetCode] 923. 3Sum With Multiplicity 三数之和的多种情况

• 2019 年 11 月 29 日
• 笔记

给定一个整数数组 A，以及一个整数 target 作为目标值，返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。

由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。

示例 1：

输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8 输出：20 解释： 按值枚举（A[i]，A[j]，A[k]）： (1, 2, 5) 出现 8 次； (1, 3, 4) 出现 8 次； (2, 2, 4) 出现 2 次； (2, 3, 3) 出现 2 次。 示例 2：

输入：A = [1,1,2,2,2,2], target = 5 输出：12 解释： A[i] = 1，A[j] = A[k] = 2 出现 12 次： 我们从 [1,1] 中选择一个 1，有 2 种情况， 从 [2,2,2,2] 中选出两个 2，有 6 种情况。

提示：

3 <= A.length <= 3000 0 <= A[i] <= 100 0 <= target <= 300

这道题是之前那道 3Sum 的拓展，之前那道题是说没有重复数字，而这道题却有大量的重复数字，所以每个组合可能会大量重复出现，让我们统计出所有组合的总出现次数，并对一个超大数取余。这样难度就比之前提升了不少，但是本质还是类似，都是使用双指针来解题。因为有很多重复的数字，所以将相同的数字放在一起便于统计，可以对数组进行排序，然后遍历数组，先确定一个数字 A[i]，则只需要找另外两个数字，使得其和为 sum = target-A[i]。然后使用两个指针j和k分别初始化为 i+1 和 n-1，若 A[j]+A[k] 小于 sum，则将j自增1；若 A[j]+A[k] 大于 sum，则将k自减1；若 A[j]+A[k] 正好等于 sum，则此时需要统计重复数字的个数，假设跟 A[j] 相同的数字有 left 个，跟 A[k] 相同的数字有 right 个。若 A[j] 不等于 A[k]，那么直接用 left 乘以 right 就是出现次数了，但如果 A[j] 等于 A[k]，则相当于在 left+right 中选两个数字的不同选法，就是初高中的排列组合的知识了。完事之后j要加上 left，k要减去 right，最终别忘了 res 要对超大数取余，参见代码如下：

解法一：

class Solution {  public:      int threeSumMulti(vector<int>& A, int target) {          long res = 0, n = A.size(), M = 1e9 + 7;          sort(A.begin(), A.end());          for (int i = 0; i < n - 2; ++i) {              int sum = target - A[i];              int j = i + 1, k = n - 1;              while (j < k) {                  if (A[j] + A[k] < sum) {                      ++j;                  } else if (A[j] + A[k] > sum) {                      --k;                  } else {                      int left = 1, right = 1;                      while (j + left < k && A[j + left] == A[j]) ++left;                      while (j + left <= k - right && A[k - right] == A[k]) ++right;                      res += A[j] == A[k] ? (k - j + 1) * (k - j) / 2 : left * right;                      j += left;                      k -= right;                  }              }          }          return res % M;      }  };

我们也可以换一种思路来解题，首先使用一个 HashMap 统计出每一个数字和其出现次数之间的映射，注意这里次数最好设定为长整型 long，因为之后做乘法的时候有可能会超过整型最大值，然后遍历 HashMap 中所有的任意的两个数字组合i和j，则第三个数字k可由 target-i-j 计算得到，若k不在 HashMap 中，则说明该组合不存在，直接跳过。若 i，j，k 三个数字相等，相当于在 numCnt[i] 中任选3个数字的方法，还是排列组合的知识；若i和j相等，但不等于k，则是在 numCnt[i] 中任选2个数字的方法个数再乘以 numCnt[k]；若三个数字都不相同，则直接用这三个数字 numCnt[i]，numCnt[j]，numCnt[k] 相乘即可，最终别忘了 res 要对超大数取余，参见代码如下：

解法二：

class Solution {  public:      int threeSumMulti(vector<int>& A, int target) {          long res = 0, M = 1e9 + 7;          unordered_map<int, long> numCnt;          for (int num : A) ++numCnt[num];          for (auto a : numCnt) {              for (auto b : numCnt) {                  int i = a.first, j = b.first, k = target - i - j;                  if (!numCnt.count(k)) continue;                  if (i == j && j == k) {                      res += numCnt[i] * (numCnt[i] - 1) * (numCnt[i] - 2) / 6;                  } else if (i == j && j != k) {                      res += numCnt[i] * (numCnt[i] - 1) / 2 * numCnt[k];                  } else if (i < j && j < k) {                      res += numCnt[i] * numCnt[j] * numCnt[k];                  }              }          }          return res % M;      }  };

接下来看一种更加简洁的解法，还是使用一个 HashMap 建立数字跟其出现次数之间的映射，但是这里并不是建立原数组每个数字跟其出现次数之间的映射，而是建立数组中任意两个数字之和的出现次数的映射，该数字之和出现了几次，就说明有多少个不同的两个数组合。那么此时遍历每个数字 A[i]，将 numCnt[target-A[i]] 加入结果中，因为和为 target-A[i] 的每个双数组合跟 A[i] 一起都可以组成符合题意的三数组合。此时由于新加入了数字 A[i]，还要从0遍历到i，将每个数字加上 A[i] 形成新的双数组合，将其和的映射值加1，这种思路真是碉堡了，参见代码如下：

解法三：

class Solution {  public:      int threeSumMulti(vector<int>& A, int target) {          int res = 0, n = A.size(), M = 1e9 + 7;          unordered_map<int, int> numCnt;          for (int i = 0; i < n; ++i) {              res = (res + numCnt[target - A[i]]) % M;              for (int j = 0; j < i; ++j) {                  int sum = A[i] + A[j];                  ++numCnt[sum];              }          }          return res;      }  };

我们也可以使用动态规划 Dynmaic Programming 来解这道题，使用一个三维的 dp 数组，其中 dp[i][j][k] 表示在范围 [0, i] 内的子数组使用k个数字能组成和为j的组合个数，则 dp[n][target][3] 即为所求，将 dp[i][0][0] 初始化为1。接下来推导状态转移方程，要新加入一个数字 A[i] 的话，那么不管这个数字能否组成新的组合，之前的所有情况这里都是继承的，即 dp[i][j][k] 至少应该加上 dp[i-1][j][k]，然后再来看 A[i] 是否能构成新的数字，但假如 j 是小于 A[i] 的，那么 A[i] 是无法组成和为j的三数之和的，只有当 j 大于等于 A[i] 时才有可能，那么就还应该加上 dp[i-1][j-A[i]][k-1] 的所有情况，它们可以跟 A[i] 组成和为j的三数组合（注意代码中由于i是从1开始的，所以是 A[i-1]），参见代码如下：

解法四：

class Solution {  public:      int threeSumMulti(vector<int>& A, int target) {          int n = A.size(), M = 1e9 + 7;          vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(target + 1, vector<int>(4)));          for (int i = 0; i <= n; ++i) dp[i][0][0] = 1;          for (int i = 1; i <= n; ++i) {              for (int j = 0; j <= target; ++j) {                  for (int k = 1; k <= 3; ++k) {                      dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % M;                      if (j >= A[i - 1]) {                          dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - A[i - 1]][k - 1]) % M;                      }                  }              }          }          return dp[n][target][3];      }  };

我们还可以优化一下空间复杂度，去掉i这一维度，因为i这维度只跟 i-1 相关，可以采用逐层覆盖的方法，但一定要注意的是，这样的中间两个 for 循环应该是从后往前遍历，不然会累加出错误的值，参见代码如下：

解法五：

class Solution {  public:      int threeSumMulti(vector<int>& A, int target) {          int n = A.size(), M = 1e9 + 7;          vector<vector<int>> dp(target + 1, vector<int>(4));          dp[0][0] = 1;          for (int i = 1; i <= n; ++i) {              for (int j = target; j >= A[i - 1]; --j) {                  for (int k = 3; k >= 1; --k) {                      dp[j][k] = (dp[j][k] + dp[j - A[i - 1]][k - 1]) % M;                  }              }          }          return dp[target][3];      }  };

Github 同步地址:

https://github.com/grandyang/leetcode/issues/923

类似题目：

3Sum Smaller

3Sum Closest

3Sum

参考资料：

https://leetcode.com/problems/3sum-with-multiplicity/

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181098/Java-O(n2)-code-Sort-and-Match.

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181128/10-lines-Super-Super-Easy-Java-Solution

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181131/C%2B%2BJavaPython-O(N-%2B-101-*-101)

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)