https://leetcode.com/problems/3sum-with-multiplicity/
X. Map store pair sum
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181128/10-lines-Super-Super-Easy-Java-Solution
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181131/C%2B%2BJavaPython-O(N-%2B-101-*-101)
X. 3 pointers
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181098/Java-O(n2)-code-Sort-and-Match.
X. DP
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)
Then
X. https://zxi.mytechroad.com/blog/math/leetcode-923-3sum-with-multiplicity/
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 <= 30000 <= A[i] <= 1000 <= target <= 300
X. Map store pair sum
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181128/10-lines-Super-Super-Easy-Java-Solution
public int threeSumMulti(int[] A, int target) {
Map<Integer, Integer> map = new HashMap<>();
int res = 0;
int mod = 1000000007;
for (int i = 0; i < A.length; i++) {
res = (res + map.getOrDefault(target - A[i], 0)) % mod;
for (int j = 0; j < i; j++) {
int temp = A[i] + A[j];
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
}
return res;
}
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)
public int threeSumMulti(int[] A, int target) {
Map<Integer, Long> map = new HashMap<>();
for (int a : A) {
map.put(a, map.getOrDefault(a, 0l) + 1);
}
long result = 0;
int M = (int)1e9 + 7;
for (int a : map.keySet()) {
for (int b : map.keySet()) {
if (b < a || a == b && map.get(a) == 1) {
continue;
}
int c = target - a - b;
if (c < b || !map.containsKey(c)) {
continue;
}
if (a == b && b == c) {
if (map.get(a) == 2) {
continue;
}
result += nCk(map.get(a), 3);
} else if (a == b) {
result += nCk(map.get(a), 2) * map.get(c);
} else if (b == c) {
if (map.get(b) == 1) {
continue;
}
result += nCk(map.get(b), 2) * map.get(a);
} else {
result += (map.get(a) * map.get(b) * map.get(c));
}
result %= M;
}
}
return (int)result;
}
private long nCk(long n, int k) {
if (k == 3) {
return (n * (n - 1) * (n - 2)) / 6;
} else {
return n * (n - 1) / 2;
}
}
Count the occurrence of each number.
using hashmap or array up to you.
using hashmap or array up to you.
Loop
loop
check if
i on all numbers,loop
j on all numbers,check if
k = target - i - j is valid.
Add the number of this combination to result.
3 cases covers all possible combination:
3 cases covers all possible combination:
i == j == ki == j != ki < k && j < k
Time Complexity:
But
So my solution is
3 <= A.length <= 3000, so N = 3000But
0 <= A[i] <= 100So my solution is
O(N + 101 * 101) public int threeSumMulti(int[] A, int target) {
long[] c = new long[101];
for (int a : A) c[a]++;
long res = 0;
for (int i = 0; i <= 100; i++)
for (int j = i; j <= 100; j++) {
int k = target - i - j;
if (k > 100 || k < 0) continue;
if (i == j && j == k)
res += c[i] * (c[i] - 1) * (c[i] - 2) / 6;
else if (i == j && j != k)
res += c[i] * (c[i] - 1) / 2 * c[k];
else if (j < k)
res += c[i] * c[j] * c[k];
}
return (int)(res % (1e9 + 7));
}
X. 3 pointers
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181098/Java-O(n2)-code-Sort-and-Match.
while (j + l < k && A[j + l] == A[j]) { ++l; }
while (j < k - r && A[k - r] == A[k]) { ++r; }
solving the duplicated cases is quite impressive, that is the solution I am looking for
private static final int m = 1_000_000_007;
public int threeSumMulti(int[] A, int target) {
Arrays.sort(A);
int res = 0;
for (int i = 0; i < A.length - 2; ++i) {
int j = i + 1;
int k = A.length - 1;
while (j < k) {
if (A[j] + A[k] < target - A[i]) { ++j; }
else if (A[j] + A[k] > target - A[i]) { --k; }
else {
if (A[j] == A[k]) {
// If A[j...k] are all equal, then there are C(k - j + 1, 2)
// combinations that meet the requirement.
res = (res + (k - j + 1) * (k - j) / 2) % m;
break;
}
int l = 1, r = 1;
while (j + l < k && A[j + l] == A[j]) { ++l; } // l: number of elements equal to A[j].
while (j < k - r && A[k - r] == A[k]) { ++r; } // r: number of elements equal to A[k].
res = (res + l * r) % m; // found l * r cases that meet the requirement.
j += l; // forward j by l steps.
k -= r; // backward k by r steps.
}
}
}
return res;
}X. DP
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)
dp[i][j][k] represents number of combinations using k numbers within A[0] ... A[i] with the sum of j.Then
dp[n][target][3] is the result. O(n * target) public int threeSumMulti(int[] A, int target) {
int n = A.length, M = (int)1e9 + 7;
int[][][] dp = new int[n + 1][target + 1][4];
for (int i = 0; i <= n; i++) {
dp[i][0][0] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= target; j++) {
for (int k = 1; k <= 3; k++) {
dp[i + 1][j][k] = dp[i][j][k];
dp[i + 1][j][k] %= M;
if (j >= A[i]) {
dp[i + 1][j][k] += dp[i][j - A[i]][k - 1];
dp[i + 1][j][k] %= M;
}
}
}
}
return dp[n][target][3];
}
Time complexity: O(n + |target|^2)
Space complexity: O(|target|)# step1 统计数组中每个元素出现的次数
一个元素I出现的次数记为count(I)
# step2 分类
记：I=A[i], J=A[j], K=A[k], C(count(I),3) 表示从count(I)个数中取3个的组合数
I=J=K C(count(I), 3)
I=J!=K C(count(I), 2) * count(K)
I!=J=K count(I) * C(count(K), 2)
I!=J!=K count(I) * count(J) * count(K)
# 复杂度
Time complexity: O(n + target^2)
Space complexity: O(100)
下面是参考视频中的截图，其中的i,j,k是数而不是index
public int threeSumMulti(int[] A, int target) {
int MOD = 1_000_000_007; // 因为最大数为10^9+7
// 计算数组中不同元素出现的个数 因为 0 <= A[i] <=100
long[] c = new long[101]; // 定义成long，在计算中不用转换
for (int a : A) c[a]++;
long ans = 0;
for (int i = 0; i <= target; i++) {
for (int j = i; j <= target; j++) {
int k = target - i - j;
if (k < 0 || k >= c.length || k < j) continue;
if (c[i] == 0 || c[j] == 0 || c[k] == 0) 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];
}
ans %= MOD;
}
}
return (int)ans;
}
public int threeSumMulti(int[] A, int target) {
int MOD = 1_000_000_007;
long ans = 0;
Arrays.sort(A);
for (int i = 0; i < A.length; ++i) {
// We'll try to find the number of i < j < k
// with A[j] + A[k] == T, where T = target - A[i].
// The below is a "two sum with multiplicity".
int T = target - A[i];
int j = i + 1, k = A.length - 1;
while (j < k) {
// These steps proceed as in a typical two-sum.
if (A[j] + A[k] < T)
j++;
else if (A[j] + A[k] > T)
k--;
else if (A[j] != A[k]) { // We have A[j] + A[k] == T.
// Let's count "left": the number of A[j] == A[j+1] == A[j+2] == ...
// And similarly for "right".
int left = 1, right = 1;
while (j + 1 < k && A[j] == A[j + 1]) {
left++;
j++;
}
while (k - 1 > j && A[k] == A[k - 1]) {
right++;
k--;
}
ans += left * right;
ans %= MOD;
j++;
k--;
} else {
// M = k - j + 1
// We contributed M * (M-1) / 2 pairs.
ans += (k - j + 1) * (k - j) / 2;
ans %= MOD;
break;
}
}
}
return (int) ans;
}
public int threeSumMulti(int[] A, int target) {
int MOD = 1_000_000_007;
long[] count = new long[101];
for (int x : A)
count[x]++;
long ans = 0;
// All different
for (int x = 0; x <= 100; ++x)
for (int y = x + 1; y <= 100; ++y) {
int z = target - x - y;
if (y < z && z <= 100) {
ans += count[x] * count[y] * count[z];
ans %= MOD;
}
}
// x == y != z
for (int x = 0; x <= 100; ++x) {
int z = target - 2 * x;
if (x < z && z <= 100) {
ans += count[x] * (count[x] - 1) / 2 * count[z];
ans %= MOD;
}
}
// x != y == z
for (int x = 0; x <= 100; ++x) {
if (target % 2 == x % 2) {
int y = (target - x) / 2;
if (x < y && y <= 100) {
ans += count[x] * count[y] * (count[y] - 1) / 2;
ans %= MOD;
}
}
}
// x == y == z
if (target % 3 == 0) {
int x = target / 3;
if (0 <= x && x <= 100) {
ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
ans %= MOD;
}
}
return (int) ans;
}
public int threeSumMulti(int[] A, int target) {
int MOD = 1_000_000_007;
// Initializing as long saves us the trouble of
// managing count[x] * count[y] * count[z] overflowing later.
long[] count = new long[101];
int uniq = 0;
for (int x : A) {
count[x]++;
if (count[x] == 1)
uniq++;
}
int[] keys = new int[uniq];
int t = 0;
for (int i = 0; i <= 100; ++i)
if (count[i] > 0)
keys[t++] = i;
long ans = 0;
// Now, let's do a 3sum on "keys", for i <= j <= k.
// We will use count to add the correct contribution to ans.
for (int i = 0; i < keys.length; ++i) {
int x = keys[i];
int T = target - x;
int j = i, k = keys.length - 1;
while (j <= k) {
int y = keys[j], z = keys[k];
if (y + z < T) {
j++;
} else if (y + z > T) {
k--;
} else { // # x+y+z == T, now calc the size of the contribution
if (i < j && j < k) {
ans += count[x] * count[y] * count[z];
} else if (i == j && j < k) {
ans += count[x] * (count[x] - 1) / 2 * count[z];
} else if (i < j && j == k) {
ans += count[x] * count[y] * (count[y] - 1) / 2;
} else { // i == j == k
ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
}
ans %= MOD;
j++;
k--;
}
}
}
return (int) ans;
}
