链接：https://leetcode-cn.com/problems/3sum-with-multiplicity/
难度：medium
解题思路：寻找3个数和为某数的总共情况。为了应对3000个0找target为0的这种case，对数组进行了merge，用map存储数字的个数。递归的实现，整体还是比较清晰的。
里面涉及到3种情况：
- 取3个不同数字
- 取2次某个数字和1次另外个数字，涉及到组合n个数取2个的n * (n - 1) / 2
- 取3次某相同数字，涉及到组合n个数取3个的n * (n - 1) * (n - 2) / 6
func threeSumMulti(A []int, target int) int {
m := map[int]int{}
d := []int{}
for _, ele := range A {
if v, ok := m[ele]; ok {
m[ele] = v + 1
} else {
m[ele] = 1
d = append(d, ele)
}
}
return lookup3(d, m, 0, 0, 0, target) % 1000000007
}
func lookup3(a []int, m map[int]int, idx int, count int, sum int, target int) int {
if sum == target && count == 3 {
return 1
}
if idx >= len(a) || sum > target || count >= 3 {
return 0
}
total := 0
num := m[a[idx]]
// count idx
result := lookup3(a, m, idx + 1, count + 1, sum + a[idx], target)
total += result * num
// count 2 times for idx
if num > 1 && count <= 1 {
result = lookup3(a, m, idx + 1, count + 2, sum + 2 * a[idx], target)
total += result * num * (num - 1) / 2
}
// count 3 times for idx
if num > 2 && count == 0 && 3 * a[idx] == target {
total += num * (num - 1) * (num - 2) / 6
}
// skip idx
total += lookup3(a, m, idx + 1, count, sum, target)
return total
}
执行用时 :72 ms, 在所有 Go 提交中击败了12.50%的用户
内存消耗 :3.4 MB, 在所有 Go 提交中击败了100.00%的用户
