题目
Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.
As the answer can be very large, return it modulo 10^9 + 7.
解题思路
- 统计每个数出现的次数，枚举两个数判断第三个数是否出现在计数器中，并且要求三个数的顺序，通过组合数求所有的可能数
- 先排序，枚举第一个数，剩余的数相当于做一个Two Sum
代码
class Solution:
def threeSumMulti(self, arr: List[int], target: int) -> int:
res = 0
MOD = 10**9 + 7
ct = Counter(arr)
for x in ct:
for y in ct:
if x > y:
continue
z = target - x - y
if y <= z and z in ct:
if x == y == z:
res += ct[x] * (ct[x] - 1) * (ct[x] - 2) // 6
elif x == y:
res += ct[x] * (ct[x] - 1) * ct[z] // 2
elif x == z:
res += ct[x] * (ct[x] - 1) * ct[y] // 2
elif y == z:
res += ct[x] * ct[y] * (ct[y] - 1) // 2
else:
res += ct[x] * ct[y] * ct[z]
return res % MOD
