class Solution {
public:
int threeSumMulti(vector<int>& arr, int target) {
}
};
923. 三数之和的多种可能
给定一个整数数组 arr ，以及一个整数 target 作为目标值，返回满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。
由于结果会非常大，请返回 109 + 7 的模。
示例 1：
输入：arr = [1,1,2,2,3,3,4,4,5,5], target = 8 输出：20 解释： 按值枚举(arr[i], arr[j], arr[k])： (1, 2, 5) 出现 8 次； (1, 3, 4) 出现 8 次； (2, 2, 4) 出现 2 次； (2, 3, 3) 出现 2 次。
示例 2：
输入：arr = [1,1,2,2,2,2], target = 5 输出：12 解释： arr[i] = 1, arr[j] = arr[k] = 2 出现 12 次： 我们从 [1,1] 中选择一个 1，有 2 种情况， 从 [2,2,2,2] 中选出两个 2，有 6 种情况。
提示：
3 <= arr.length <= 30000 <= arr[i] <= 1000 <= target <= 300原站题解
golang 解法, 执行用时: 32 ms, 内存消耗: 3 MB, 提交时间: 2023-09-20 10:48:41
const mod = 1000000007
func threeSumMulti(A []int, target int) (result int) {
sort.Ints(A)
l := len(A)
for k, v := range A {
newTarget := target - v // 新的目标值
left, right := k+1, l-1
for left < right {
sum := A[left] + A[right]
if sum < newTarget {
left++
continue
}
if sum > newTarget {
right--
continue
}
// 和值等于目标值
// 如果左右值相等，排列组合数如下
if A[left] == A[right] {
result += (right - left + 1) * (right - left) / 2
result %= mod
break
}
// 如果左右值不等，排列组合数如下
leftSameCount, rightSameCount := 1, 1
for left+1 < right && A[left] == A[left+1] {
leftSameCount++
left++
}
for right-1 > left && A[right] == A[right-1] {
rightSameCount++
right--
}
result += leftSameCount * rightSameCount
result %= mod
left++
right--
}
}
return result
}
// dp
func threeSumMulti2(arr []int, target int) int {
n := len(arr)
cnt := make([]map[int]int, n)
for i := range cnt {
cnt[i] = map[int]int{}
}
for i := 1; i < n; i++ {
for j := i-1; j >= 0; j-- {
cnt[i][arr[i] + arr[j]]++
}
}
ans, mod := 0, int(1e9+7)
for i := 1; i < n; i++ {
for j := i+1; j < n; j++ {
ans += cnt[i][target-arr[j]]
ans %= mod
}
}
return ans
}
cpp 解法, 执行用时: 152 ms, 内存消耗: 20.7 MB, 提交时间: 2023-09-20 10:47:22
class Solution {
public:
int mod = 1e9 + 7;
int threeSumMulti(vector<int>& A, int target) {
//dp[i][j][k]表示考虑前i个数时，从中选出j个数，组成k大小的方案数
int n = A.size();
int dp[n + 1][4][target + 1];
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; i ++ ) dp[i][0][0] = 1;
//这里要从1开始，因为前0个数是初始的条件
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= 3; j ++ )
for (int k = 0; k <= target; k ++ )
{
//这里用A[i - 1]是因为从1开始枚举下标，对于A数组来说，要从0开始，因此错后一个
if (k >= A[i - 1]) dp[i][j][k] =(dp[i][j][k] + dp[i - 1][j - 1][k - A[i - 1]]) % mod;
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % mod;
}
//最终答案就是考虑前n个数时，选择其中3个数，组成target大小的方案数
return dp[n][3][target];
}
};
java 解法, 执行用时: 46 ms, 内存消耗: 41.9 MB, 提交时间: 2023-09-20 10:46:44
class Solution {
// 方法一：三指针
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 threeSumMulti2(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 threeSumMulti3(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;
}
}
python3 解法, 执行用时: 72 ms, 内存消耗: 16 MB, 提交时间: 2023-09-20 10:44:28
class Solution:
def threeSumMulti(self, A: List[int], target: int) -> int:
MOD = 10**9 + 7
count = collections.Counter(A) # 频率
keys = sorted(count) # key排序
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 i, x in enumerate(keys):
T = target - x
j, k = i, len(keys) - 1
while j <= k:
y, z = keys[j], keys[k]
if y + z < T:
j += 1
elif y + z > T:
k -= 1
else: # x+y+z == T, now calculate the size of the contribution
if i < j < k:
ans += count[x] * count[y] * count[z]
elif i == j < k:
ans += count[x] * (count[x] - 1) // 2 * count[z]
elif i < 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
j += 1
k -= 1
return ans % MOD
python3 解法, 执行用时: 2768 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-20 10:38:55
'''
三指针
两数之和，双指针可行
'''
class Solution:
def threeSumMulti(self, A: List[int], target: int) -> int:
MOD = 10**9 + 7
ans = 0
A.sort() # 排序
for i, x in enumerate(A):
# 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".
T = target - A[i]
j, k = i+1, len(A) - 1
while j < k:
# These steps proceed as in a typical two-sum.
if A[j] + A[k] < T:
j += 1
elif A[j] + A[k] > T:
k -= 1
# These steps differ:
elif 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".
left = right = 1
while j + 1 < k and A[j] == A[j+1]:
left += 1
j += 1
while k - 1 > j and A[k] == A[k-1]:
right += 1
k -= 1
# We contributed left * right many pairs.
ans += left * right
ans %= MOD
j += 1
k -= 1
else:
# M = k - j + 1
# We contributed M * (M-1) / 2 pairs.
ans += (k-j+1) * (k-j) // 2
ans %= MOD
break
return ans
python3 解法, 执行用时: 72 ms, 内存消耗: 16 MB, 提交时间: 2023-09-20 10:38:25
class Solution:
def threeSumMulti(self, A: List[int], target: int) -> int:
MOD = 10**9 + 7
count = [0] * 101
for x in A:
count[x] += 1
ans = 0
# All different
for x in range(101):
for y in range(x+1, 101):
z = target - x - y
if y < z <= 100:
ans += count[x] * count[y] * count[z]
ans %= MOD
# x == y
for x in range(101):
z = target - 2*x
if x < z <= 100:
ans += count[x] * (count[x] - 1) // 2 * count[z]
ans %= MOD
# y == z
for x in range(101):
if (target - x) % 2 == 0:
y = (target - x) // 2
if x < y <= 100:
ans += count[x] * count[y] * (count[y] - 1) // 2
ans %= MOD
# x == y == z
if target % 3 == 0:
x = target // 3
if 0 <= x <= 100:
ans += count[x] * (count[x] - 1) * (count[x] - 2) // 6
ans %= MOD
return ans