三数之和的多种可能

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

先一遍扫数组数清每个值出现几次。现在读到 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 的异同。