三数之和的多种可能 图解题解

这道题到底在问什么

输入

arr=[1,2,3,3,3,4,4], target=9

输出

8

先想最直接的笨办法

记住口诀：先数清每个值几次，再枚举三个值，按相不相等用组合数算搭配。下面每帧都在套它。（动画第 3 步）

最优解：一步一步想明白

1. 3记住口诀：先数清每个值几次，再枚举三个值，按相不相等用组合数算搭配。下面每帧都在套它。
2. 4先一遍扫数组数清每个值出现几次。现在读到 arr[0] = 1，把它在计数表里的次数加到 1。
3. 5先一遍扫数组数清每个值出现几次。现在读到 arr[1] = 2，把它在计数表里的次数加到 1。
4. 6先一遍扫数组数清每个值出现几次。现在读到 arr[2] = 3，把它在计数表里的次数加到 1。
5. 7先一遍扫数组数清每个值出现几次。现在读到 arr[3] = 3，把它在计数表里的次数加到 2。
6. 8先一遍扫数组数清每个值出现几次。现在读到 arr[4] = 3，把它在计数表里的次数加到 3。
7. 9先一遍扫数组数清每个值出现几次。现在读到 arr[5] = 4，把它在计数表里的次数加到 1。
8. 10先一遍扫数组数清每个值出现几次。现在读到 arr[6] = 4，把它在计数表里的次数加到 2。
9. 11计数表全部建好：值 1 有 1 个、2 有 1 个、3 有 3 个、4 有 2 个。接下来枚举三个值 a ≤ b ≤ c，看哪些组合相加正好等于 9。
10. 12开始枚举。先看 (1, 1, 2)，三个值相加是 4，不等于 9，这组跳过。
11. 13再看 (1, 2, 3)，和是 6，没到 9，差一点，跳过。
12. 14再看 (1, 3, 4)，和是 8，没到 9，差一点，跳过。
13. 15(1, 4, 4) 三个值相加正好是 9，命中！高亮的就是这几个值所在的「桶」。下一帧算它能凑出多少种下标搭配。
14. 16这组是「两值相同」。一个 1 加两个 4：cnt[1] × C(2,2) = 1 × 1 = 1。把这 1 种搭配加进答案，ans 现在是 1。
15. 17再看 (2, 2, 4)，和是 8，没到 9，差一点，跳过。
16. 18(2, 3, 4) 三个值相加正好是 9，命中！高亮的就是这几个值所在的「桶」。下一帧算它能凑出多少种下标搭配。
17. 19这组是「三值都不同」。三个值都不同：cnt[2] × cnt[3] × cnt[4] = 1 × 3 × 2 = 6。把这 6 种搭配加进答案，ans 现在是 7。
18. 20再看 (2, 4, 4)，和是 10，比 9 大，跳过。
19. 21(3, 3, 3) 三个值相加正好是 9，命中！高亮的就是这几个值所在的「桶」。下一帧算它能凑出多少种下标搭配。
20. 22这组是「三值相同」。三个值都是 3：从 3 个 3 里挑 3 个，组合数 C(3,3) = 1。把这 1 种搭配加进答案，ans 现在是 8。
21. 23再看 (3, 3, 4)，和是 10，比 9 大，跳过。
22. 24这里只展示部分代表性组合，但所有命中 9 的组合都完整演了：三组分别贡献 1、6、1，合计 8。动画用的是「按值枚举 a≤b≤c + 组合数」的直观版：枚举全部三值组合，cnt 不足或和不等于 9 的直接跳过。下一帧 step 25 的参考代码则是等价的「下标版」（枚举中间下标 j、左侧下标 i，再用 cnt 查右侧数量），两者结果一致，但复杂度表达不同：动画按值枚举版是 O(n + K²)，参考代码下标版是 O(n²)。这就是满足条件的下标元组总数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        mod = 10**9 + 7
        cnt = Counter(arr)
        ans = 0
        for j, b in enumerate(arr):
            cnt[b] -= 1
            for a in arr[:j]:
                c = target - a - b
                ans = (ans + cnt[c]) % mod
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int threeSumMulti(vector<int>& arr, int target) {
        const int mod = 1e9 + 7;
        int cnt[101]{};
        for (int x : arr) {
            ++cnt[x];
        }
        int n = arr.size();
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            --cnt[arr[j]];
            for (int i = 0; i < j; ++i) {
                int c = target - arr[i] - arr[j];
                if (c >= 0 && c <= 100) {
                    ans = (ans + cnt[c]) % mod;
                }
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int threeSumMulti(int[] arr, int target) {
        final int mod = (int) 1e9 + 7;
        int[] cnt = new int[101];
        for (int x : arr) {
            ++cnt[x];
        }
        int n = arr.length;
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            --cnt[arr[j]];
            for (int i = 0; i < j; ++i) {
                int c = target - arr[i] - arr[j];
                if (c >= 0 && c < cnt.length) {
                    ans = (ans + cnt[c]) % mod;
                }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问