Problem
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
Solution: Math / Combination
Time complexity: O(n + |target|^2)
Space complexity: O(|target|)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua, runtime: 4 ms class Solution { public: int threeSumMulti(vector<int>& A, int target) { constexpr int kMaxN = 100; constexpr int kMod = 1e9 + 7; vector<long> c(kMaxN + 1, 0); for (int a : A) ++c[a]; long ans = 0; for (int i = 0; i <= target; ++i) { for (int j = i; j <= target; ++j) { const int k = target - i - j; if (k < 0 || k >= c.size() || k < j) continue; if (!c[i] || !c[j] || !c[k]) continue; if (i == j && j == k) ans += (c[i] - 2) * (c[i] - 1) * c[i] / 6; else if (i == j && j != k) ans += c[i] * (c[i] - 1) / 2 * c[k]; else if (i != j && j == k) ans += c[i] * (c[j] - 1) * c[j] / 2; else ans += c[i] * c[j] * c[k]; } } return ans % kMod; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment