Given an integer array A, and an integer target, return the number of tuples i,j,k such that i<j<k and A[i]+A[j]+A[k]==target.
As the answer can be very large, return it modulo 10^9+7.
Example 1:
Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation:
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.
Example 2:
Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation:
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.
Note:
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)
LeetCode All in One 題目講解匯總(持續更新中...)