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

数的是下标元组，不是不同的值组合

给数组 arr 和目标 target，数出多少组下标 (i, j, k) 满足 i ＜ j ＜ k、且 arr[i]+arr[j]+arr[k]=target，答案对 10^9+7 取模。数的是下标元组个数，不是不同值组合个数：同一个值出现多次，用不同下标挑出来算不同答案。题面 arr=[1,2,3,3,3,4,4]、target=9 答案 8，因为 3 有三个、4 有两个，一种值搭配摊出好几组。取模是防组合太多溢出。

三重循环枚举下标，长度到 3000 就跑不完

上来先写三重循环：i、j、k 各扫下标，凑齐就看和等不等于 target。可 arr 长度到 3000，O(n³) 量级 2.7×10¹⁰，判题机就超时。它把每组下标单独试一遍，可值就那么几个——数组里的数全落在 0 到 100 这段值域里，满打满算才 101 种。没必要盯着几千个下标枚举。

值域只有 101，把枚举从下标搬到值上

改成盯着值来数。先扫一遍 arr，用计数表数清每个值出现几次（记作 cnt，cnt[3] 就是 3 的个数）。之后枚举三个值 a≤b≤c，只要 a+b+c=target 就是一组命中的值搭配。这组值对应多少种下标取法，看三值是否相等——相等的值只能从同一批下标里挑，得用组合数 C(m,r)，也就是从 m 个里挑 r 个有几种挑法，不能简单相乘。

三个值相不相等，组合数分四种情形算

按 a、b、c 相不相等分四种。三个都不同，各自挑一个乘起来 cnt[a]×cnt[b]×cnt[c]。前两个相同 a=b≠c，从 cnt[a] 里挑 2 个再挑一个 c，是 C(cnt[a],2)×cnt[c]。后两个相同 a≠b=c，对称地 cnt[a]×C(cnt[c],2)。三个全相同，挑 3 个即 C(cnt[a],3)。每算一组就累加，每次都对 10^9+7 取模，别攒到最后。

题面这个数组，8 组是怎么数出来的

顺着题面 arr=[1,2,3,3,3,4,4]、target=9 走一遍。先数出 cnt：1 有 1 个、2 有 1 个、3 有 3 个、4 有 2 个。枚举 a≤b≤c 里和为 9 的，只三组命中。(1,4,4) 后两位相同：cnt[1]×C(cnt[4],2)=1×C(2,2)=1。(2,3,4) 三个都不同：cnt[2]×cnt[3]×cnt[4]=1×3×2=6。(3,3,3) 三个全相同：C(cnt[3],3)=C(3,3)=1。三组相加 1+6+1=8，正是题面给的 8。(1,1,2)、(2,4,4) 等和不为 9 的跳过。

相同值用乘法，会把同一个下标选两回

过程先 O(n) 建 cnt，再枚举 K 种不同值（K≤101）做 O(K²) 配对，合起来 O(n+K²)，值域固定时近似线性；计数表 101 格，空间 O(1)。相同值那支图省事写 cnt×cnt，会把同一下标当两个元素配、把顺序数两遍，多出不存在的搭配。取模若只在返回前做一次，累加途中的和会超出整型范围、算出乱数，得边加边取。target 凑不齐时答案自然是 0，不用特判。

Python

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

C++

#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;
    }
};

Java

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;
    }
}