题目描述
思路解析
一句话答案：LeetCode 923 三数之和的多种可能：值域只有 0 到 100，先用计数表数清每个值几次，再枚举三个值 a≤b≤c、按相等情况用组合数累加下标搭配，边加边对 1e9+7 取模。时间 O(n+K²)、空间 O(1)。
数的是下标元组，不是不同的值组合
给数组 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，不用特判。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住口诀：先数清每个值几次，再枚举三个值，按相不相等用组合数算搭配。下面每帧都在套它。
先一遍扫数组数清每个值出现几次。现在读到 arr[0] = 1，把它在计数表里的次数加到 1。
先一遍扫数组数清每个值出现几次。现在读到 arr[1] = 2，把它在计数表里的次数加到 1。
先一遍扫数组数清每个值出现几次。现在读到 arr[2] = 3，把它在计数表里的次数加到 1。
先一遍扫数组数清每个值出现几次。现在读到 arr[3] = 3，把它在计数表里的次数加到 2。
先一遍扫数组数清每个值出现几次。现在读到 arr[4] = 3，把它在计数表里的次数加到 3。
先一遍扫数组数清每个值出现几次。现在读到 arr[5] = 4，把它在计数表里的次数加到 1。
先一遍扫数组数清每个值出现几次。现在读到 arr[6] = 4，把它在计数表里的次数加到 2。
计数表全部建好：值 1 有 1 个、2 有 1 个、3 有 3 个、4 有 2 个。接下来枚举三个值 a ≤ b ≤ c，看哪些组合相加正好等于 9。
开始枚举。先看 (1, 1, 2)，三个值相加是 4，不等于 9，这组跳过。
再看 (1, 2, 3)，和是 6，没到 9，差一点，跳过。
再看 (1, 3, 4)，和是 8，没到 9，差一点，跳过。
(1, 4, 4) 三个值相加正好是 9，命中！高亮的就是这几个值所在的「桶」。下一帧算它能凑出多少种下标搭配。
这组是「两值相同」。一个 1 加两个 4：cnt[1] × C(2,2) = 1 × 1 = 1。把这 1 种搭配加进答案，ans 现在是 1。
再看 (2, 2, 4)，和是 8，没到 9，差一点，跳过。
(2, 3, 4) 三个值相加正好是 9，命中！高亮的就是这几个值所在的「桶」。下一帧算它能凑出多少种下标搭配。
这组是「三值都不同」。三个值都不同：cnt[2] × cnt[3] × cnt[4] = 1 × 3 × 2 = 6。把这 6 种搭配加进答案，ans 现在是 7。
再看 (2, 4, 4)，和是 10，比 9 大，跳过。
(3, 3, 3) 三个值相加正好是 9，命中！高亮的就是这几个值所在的「桶」。下一帧算它能凑出多少种下标搭配。
这组是「三值相同」。三个值都是 3：从 3 个 3 里挑 3 个，组合数 C(3,3) = 1。把这 1 种搭配加进答案，ans 现在是 8。
再看 (3, 3, 4)，和是 10，比 9 大，跳过。
这里只展示部分代表性组合，但所有命中 9 的组合都完整演了：三组分别贡献 1、6、1，合计 8。动画用的是「按值枚举 a≤b≤c + 组合数」的直观版：枚举全部三值组合，cnt 不足或和不等于 9 的直接跳过。下一帧 step 25 的参考代码则是等价的「下标版」（枚举中间下标 j、左侧下标 i，再用 cnt 查右侧数量），两者结果一致，但复杂度表达不同：动画按值枚举版是 O(n + K²)，参考代码下标版是 O(n²)。这就是满足条件的下标元组总数。
边界先想清：无解返回 0、三值全相同走 C(cnt,3)、target 过小无解。
面试重点：认出「值域小 → 计数 + 组合」这个母题，并能说清和 3Sum 的异同。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n + K²)，动画按值枚举：先扫一遍 arr 建 cnt 是 O(n)，再枚举不同值种类 K≤101 是 O(K²);参考代码下标版是 O(n²)
- 空间：O(1)，计数数组大小固定 101（值域 0 到 100）
易错点
面试追问把动画讲成自己的话
追问这题和经典 3Sum（两数之和的双指针版）有什么联系和区别？
追问如果不用组合数，能不能用参考代码那种两层循环？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
令牌放置
LeetCode 948 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题