[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)