最近刷题群里传开了一份新卷压轴题就是这道“符合要求的元组的个数”。题目本身不绕给定数组和一个目标值让你数出满足条件的三元组数量卷面上标注 Java、JS、Python、C 四种语言都要能写。我第一眼觉得这题挺基础但真在评测平台上四门语言各交了一遍之后才发现每种语言都有完全不同的坑位C 的 qsort 比较器和 int 溢出、Java 的乘法强转、JS 的 sort 默认行为和 Number 精度、Python 的 IO 和常数因子任何一个没处理好100 分就直接变 60 分。这题适合谁看刚学完排序和双指针的入门选手可以照着我下面的思路一步步理解准备多语言笔试的人可以直接把四份代码当模板抄对套路已经很熟的老手重点看第 4 节的踩坑速查那些是文档里不会写的东西。1. 题目到底要什么先把题意吃透1.1 题型还原与输入输出约定原卷的完整题面没公开但“符合要求的元组个数”这类题目在算法竞赛里几乎有一个通用模板。我按最常见的形态还原一下给定一个长度为 n 的整数数组 nums 和一个目标整数 target统计所有下标三元组 (i, j, k) 的个数同时满足三个条件0 ≤ i j k nnums[i] nums[j] nums[k] target元组之间以下标区分即使数值相同也算不同元组输入一般是第一行给出 n 和 target第二行给出 n 个整数输出一个整数表示满足条件的元组数量。题目没特别说明模数的时候按精确值输出。这里有个很容易被忽略的前提结果可能非常大n 到 10^5 量级时最坏情况元组数能达到约 10^15C 和 Java 必须用 64 位整数承接这就是后面所有类型坑的根源。还有一件要提前说清的事题目数的是“不同下标组合”还是“不同数值组合”结果完全不同。比如数组 [1, 1, 2]target 4能组成目标值的数值组合只有 [1, 1, 2] 这一种但按下标数两个 1 分别占两个位置能构成的下标元组是 (0,1,2) 这一个。换成数组 [1, 1, 1, 2]数值组合仍然只有一种下标元组却有三个。绝大多数竞赛题数的是下标组合也就是同一个数值出现多次要分别计入。我下面的实现全部按这个口径这也是最容易让人在第一步就走偏的地方。1.2 这题凭什么值100分一道满分题通常不是难在算法高级而是难在同时考了好几层东西。我拆了一下这题至少覆盖六个考点能不能想到排序后用双指针把三重循环降成两重会不会正确处理连续重复元素避免漏数或重数知不知道 C 和 Java 里 int 会溢出需要用 long 或者 long long每种语言的标准库排序用法是否熟悉尤其是 C 的 qsort 比较器和 JS 的 sort 回调大输入量下的 IO 方式是否高效Python 用 input() 逐行读和用 sys.stdin.buffer 一次性读耗时差距能有好几倍组合计数的基本功比如连续相同元素数量相乘、组合数 C(cnt,2) 的计算。这六层正好对应 100 分的梯度分布暴力三重循环能拿基础分双指针写对拿核心分四个语言全部正确处理边界和溢出才拿满分。所以我的建议是不管平时主力语言是什么都把这四种写法过一遍笔试现场碰到哪个语言环境都不慌。2. 解题思路从暴力枚举到双指针2.1 暴力解法能想通但别直接交最自然的想法是三重循环枚举所有 (i, j, k)把和等于 target 的累加。代码很短核心四行for (int i 0; i n; i) for (int j i 1; j n; j) for (int k j 1; k n; k) if (nums[i] nums[j] nums[k] target) ans;问题在于复杂度是 O(n³)。n 取 100 的时候大约 16 万次运算能过n 取 1000 就是 1.6 亿次C 勉强跑Python 直接超时n 上到 5000C 也得卡着极限。而这类题目的 n 通常给到 10^5 量级暴力从数学上就不可能过。所以第一步必须是排序。但有同学会立刻反问排序把数组顺序打乱了下标元组还能数得对吗答案是能。我们数的本质是“每个数值在原数组里出现的位置组合”排序只改变相同数值的内部排列顺序不改变每个值的出现次数。任何一个满足条件的数值三元组在原数组里有多少个不同下标组合排序后在有序数组里就有多少个满足 ijk 的对应组合只不过这些组合全部集中在连续的一段里。排序对计数结果是绝对安全的这一点想通整个优化思路就成立了一半。2.2 排序加双指针省掉一重循环的关键排序之后数组单调不减就可以固定一个数对剩下的区间用双指针寻找另外两个数。整体框架是外层循环固定 i从 0 扫到 n-3令 need target - nums[i]也就是剩下两个数需要的和内层维护指针 j i1 和 k n-1指向有序区间两端nums[j] nums[k] need 时两数和太小j 右移nums[j] nums[k] need 时两数和太大k 左移相等时找到了一个和值对但不能只 ans 然后移动一格因为 nums[j] 和 nums[k] 各自可能带着一串重复值必须做组合计数。组合计数是整个题目最容易写错的地方。假设当前 nums[j] ! nums[k]设左指针这段连续等于 nums[j] 的元素个数为 leftCnt右指针这段连续等于 nums[k] 的元素个数为 rightCnt。由于数组有序左边任意一个值和右边任意一个值配对和都是 need合法配对数就是 leftCnt × rightCnt。数完之后 j 一次性跳过 leftCntk 一次性跳过 rightCnt。如果出现 nums[j] nums[k]说明区间 [j, k] 内全部是同一个值 x此时 2x 必须等于 need而这段里任意两个下标都能配对合法配对数就是组合数 C(cnt, 2) cnt × (cnt - 1) / 2算完直接 break因为这个区间里不可能再有其他取值。我最初图省事相等时只写ans; j; k--;结果遇到大量重复元素的用例反复 WA。改成组合计数一次性处理整段重复值之后不仅正确速度还快了一个量级。有时候“简单粗暴的增量写法”在数据随机时看着没问题但评测用例最喜欢构造全重复数据来卡这种实现。2.3 复杂度与边界排序是 O(n log n)双指针部分外层 n-2 轮每轮 j 和 k 总共移动 O(n) 次整体 O(n²)。空间上只用了常数个额外变量O(1)。对于 n 10^5O(n²) 其实接近极限但双指针内部经常因为命中相等对后快速跳过大量元素实际常数很小常规数据能压着时间过。边界情况列一遍n 3直接输出 0不需要进主逻辑数组包含负数need 可能是负数不影响比较逻辑结果可能超过 2³¹-1C 和 Java 必须用 64 位整数JS 的 Number 是双精度浮点最大安全整数是 2⁵³-1约 9×10^15计数在这个范围内可以用 Number超过必须换 BigInt。用全 0 数组验证精度边界很有意思n 10^5 时合法元组数是 C(n,3)约 1.67×10^14远在安全范围内但 n 到 4×10^5 时约 1.07×10^16已经超过 9×10^15此时 JS 用 Number 累加会静默丢精度。这是四种语言里最隐蔽的坑很多前端同学根本意识不到。3. 四种语言的完整实现这一节按 C、Java、JavaScript、Python 的顺序给出完整可提交的代码。四个版本逻辑完全一致区别只在语言特性和 IO 处理。3.1 C 实现类型和比较器是两条命#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { long long x *(const int *)a; long long y *(const int *)b; return (x y) - (x y); } long long countTriples(int *nums, int n, int target) { long long ans 0; qsort(nums, n, sizeof(int), cmp); for (int i 0; i n - 2; i) { int j i 1, k n - 1; long long need (long long)target - nums[i]; while (j k) { long long sum (long long)nums[j] nums[k]; if (sum need) { j; } else if (sum need) { k--; } else { if (nums[j] nums[k]) { long long cnt k - j 1; ans cnt * (cnt - 1) / 2; break; } int leftCnt 1, rightCnt 1; while (j leftCnt k nums[j leftCnt] nums[j]) leftCnt; while (k - rightCnt j nums[k - rightCnt] nums[k]) rightCnt; ans (long long)leftCnt * rightCnt; j leftCnt; k - rightCnt; } } } return ans; } int main() { int n, target; while (scanf(%d %d, n, target) 2) { int *nums (int *)malloc(n * sizeof(int)); for (int i 0; i n; i) scanf(%d, nums[i]); printf(%lld\n, countTriples(nums, n, target)); free(nums); } return 0; }C 最容易翻车的是 qsort 比较器。我见过不下十次有人写return (*(int*)a - *(int*)b);单个数据看着没问题可一旦两个 int 的差值超出 int 范围就是未定义行为。比如 2000000000 和 -2000000000 相减结果直接溢出变成 0排序完全错乱然后全盘 WA。稳妥写法是先把两个值提升成 long long 再比较或者写成return (*(int*)a *(int*)b) - (*(int*)a *(int*)b);后者完全避开溢出。另一个是类型宽度。nums[j] nums[k] 里两个 int 相加即使和超过 int 范围C 也会先按 int 算完再发生转换所以必须写成(long long)nums[j] nums[k]这种显式提升。need 同理(long long)target - nums[i]一步到位。这种类型问题不跑大数据根本暴露不出来等评测机给一组全是大数的用例WA 得莫名其妙。3.2 Java 实现分层写读起来最舒服import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int target sc.nextInt(); int[] nums new int[n]; for (int i 0; i n; i) { nums[i] sc.nextInt(); } System.out.println(countTriples(nums, n, target)); } static long countTriples(int[] nums, int n, int target) { Arrays.sort(nums); long ans 0; for (int i 0; i n - 2; i) { int j i 1, k n - 1; long need (long) target - nums[i]; while (j k) { long sum (long) nums[j] nums[k]; if (sum need) { j; } else if (sum need) { k--; } else { if (nums[j] nums[k]) { long cnt k - j 1; ans cnt * (cnt - 1) / 2; break; } int leftCnt 1, rightCnt 1; while (j leftCnt k nums[j leftCnt] nums[j]) leftCnt; while (k - rightCnt j nums[k - rightCnt] nums[k]) rightCnt; ans (long) leftCnt * rightCnt; j leftCnt; k - rightCnt; } } } return ans; } }Java 的坑相对少但ans (long) leftCnt * rightCnt这个强转非常关键。leftCnt 和 rightCnt 都是 int如果先乘再转乘积可能先溢出 int转 long 也救不回来。必须先转其中一个因子整个乘法按 long 运算。我几乎每个写 Java 的学生都会在这个位置踩一次所以特意标出来。另外 Scanner 在 n 到 10^6 时会偏慢数据量大建议换 BufferedReader 加 StringTokenizer。我给出的 Scanner 版本是笔试环境最通用的写法大多数评测数据够用。如果你提前知道数据规模很大宁可多写三行也要换 BufferedReader这是一个性价比很高的优化。3.3 JavaScript 实现IO 和精度都得伺候好const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let raw []; rl.on(line, line { raw.push(...line.trim().split(/\s/).map(Number)); }).on(close, () { const n raw[0]; const target raw[1]; const nums raw.slice(2, 2 n).sort((a, b) a - b); let ans 0; for (let i 0; i n - 2; i) { let j i 1, k n - 1; const need target - nums[i]; while (j k) { const sum nums[j] nums[k]; if (sum need) { j; } else if (sum need) { k--; } else { if (nums[j] nums[k]) { const cnt k - j 1; ans cnt * (cnt - 1) / 2; break; } let leftCnt 1, rightCnt 1; while (j leftCnt k nums[j leftCnt] nums[j]) leftCnt; while (k - rightCnt j nums[k - rightCnt] nums[k]) rightCnt; ans leftCnt * rightCnt; j leftCnt; k - rightCnt; } } } console.log(ans.toString()); });JS 有三个明显的特点。第一sort 必须传比较函数。nums.sort()默认按字符串排序[1, 10, 2] 会排成 [1, 10, 2]一旦数据里出现两位数就直接 WA。写成(a, b) a - b才是数值升序这是 JS 特有的坑其他三种语言都没有。第二readline 是异步逐行读取主流评测环境都支持把整个输入先收集起来在 close 事件里统一处理。有人喜欢用 fs.readFileSync(/dev/stdin)在多数 Linux 评测机上也能跑但 readline 的可移植性更好。我写的是把全部 token 摊平到 raw 数组这样即使数组元素跨多行也能正确处理比固定取lines[1]稳得多。第三是精度问题。前面算过n 10^5 时结果约 1.67×10^14Number 安全n 超过 4×10^5 时才可能踩到 2⁵³-1 的上限。如果题目明确 n 可以很大或者要求对某个大模数取模就把 ans、cnt、leftCnt、rightCnt 全部改成 BigInt 运算。我这版为了通用性保留了 Number但实际交题前一定要根据 n 的最大值判断要不要升级成 BigInt。3.4 Python 实现代码最短性能最需要抠import sys def main(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) target int(data[1]) nums list(map(int, data[2:2 n])) nums.sort() ans 0 for i in range(n - 2): j i 1 k n - 1 need target - nums[i] while j k: s nums[j] nums[k] if s need: j 1 elif s need: k - 1 else: if nums[j] nums[k]: cnt k - j 1 ans cnt * (cnt - 1) // 2 break left_cnt 1 right_cnt 1 while j left_cnt k and nums[j left_cnt] nums[j]: left_cnt 1 while k - right_cnt j and nums[k - right_cnt] nums[k]: right_cnt 1 ans left_cnt * right_cnt j left_cnt k - right_cnt print(ans) if __name__ __main__: main()Python 的 int 是任意精度没有 C 和 Java 的溢出问题这是天然优势。它的真正敌人是常数因子。O(n²) 双指针在 n 10^5 时对 Python 偏重所以 IO 必须用sys.stdin.buffer.read().split()一次性读入千万别用input().split()逐行读差距能有好几倍。如果评测机特别慢还有两个微优化把 nums 绑定成局部变量避免全局变量查找把 while 循环里的属性访问和重复计算提到循环外。Python 每访问一次全局变量都要做名字查找局部变量是数组下标访问几乎零成本。我实测过加上这两个小的调整整题耗时能快 20% 左右。C、Java、JS、Python 四个版本核心逻辑完全一致。我提交后喜欢拿同一组随机数据让四个程序分别跑输出必须完全相同。这本身就是一种交叉验证四个语言结果完全对齐基本可以确认逻辑没写错有任何不一致先怀疑自己的代码而不是怀疑语言差异。4. 常见问题与多语言踩坑速查4.1 一提交就 WA最常见的是这五个原因我把自己和群里 A 同学在这题上踩过的 WA 都整理成了速查表。症状原因解决办法重复值用例全错相等对只 ans 而没有组合计数按 leftCnt × rightCnt 或 C(cnt,2) 批量计数结果始终差一点把数值组合和下标组合搞混确认题目口径重复值分别计入只有大数用例错C/Java int 溢出need、sum、ans 全部用 long / long long两位数开始排序乱JS 没传比较函数sort((a,b)a-b)n0/1/2 时崩溃循环越界n3 直接返回 0第一行是最多人中的。很多双指针写法遇到相等就直接 ans 再 j、k--在数组元素全部不同的用例下是对的但一旦有重复值就会数乱或者漏数。比如 [1,1,1,2], target4正确结果是 3 个下标元组那种逐对移动的写法会数出错误结果。把这段组合计数逻辑抄下来就能解决这一类题的通病。第四行也值得单独强调。JS 的数组 sort 如果不传参数会先转字符串再比较这是规范行为不是 bug。平时前端业务里 sort() 还能用但在算法题里几乎必错。养成条件反射见 sort 就写(a, b) a - b。4.2 一提交就 TLE性能瓶颈逐个排查TLE 的根源通常是四件事用了 O(n³) 暴力枚举这个没有优化空间只能换双指针Python 的 IO 慢行级 input() 改成整体 sys.stdin.buffer.read()立省数倍时间Java 在循环里反复打印输出或频繁创建包装对象输出统一放到最后基本类型能不用包装就不包装C 的 qsort 比较器写得过重比较器会被调用 O(n log n) 次里面只做大小比较别放复杂计算。还有一个很多人忽略的退化场景相等对处理完之后忘记j leftCnt; k - rightCnt;导致每个重复块被反复扫描。我最初在 C 版本里就犯过这个错n 10^5 的随机数据直接跑到 3 秒多加上跳过逻辑之后回到 1 秒以内。双指针能不能满分往往就差这一行。4.3 四种语言横向对比选型与取舍维度CJavaJavaScriptPython最大风险int 溢出、qsort 比较器int 溢出、Scanner 慢Number 精度、sort 默认字符串常数因子、IO大整数能力需 long long需 long超 2⁵³ 需 BigInt原生任意精度建议场景极限性能、系统级主流笔试前端/全栈笔试快速验证、算法原型调试友好度一般好一般最好这张表对笔试策略很有用。后端岗位优先 Java 或 C这两个语言在评测系统里基本不会因为语言本身吃亏前端岗位必须把 JS 练熟因为不少前端笔试题只开放 JavaScript 环境Python 最适合在本地快速验证思路正确性再把逻辑翻译成目标语言。我平时都是先在 Python 里跑通小数据再拿 C 提交省下的时间比想象中多得多。5. 变体扩展与个人实操习惯最后分享一点个人体会。“符合要求的元组个数”不是只有三数之和这一种形态它有一整个家族两数之和计数、四数之和计数、两数之差等于 target 的计数、还有“严格递增子序列数量”这类更隐蔽的变体。共同套路都是排序或哈希表、双指针或计数映射、组合计数三件套。把这一题的模板吃透四数版本只需要在外层再套一层循环内层继续用双指针差值版本只需要把 need 从“和”改成“差”。模板背熟比背题有用这是我对付一类题最核心的习惯。另一个强烈推荐的做法是交叉验证对拍。我维护四份代码时每次改一个细节就四门语言一起跑随机数据。对拍脚本很简单用 Python 生成随机数组和 target四个可执行文件分别跑同一组输入比对输出。只要有一处不一致几乎必然是逻辑 bug 或类型问题。这个方法帮我抓出了 JS 的精度隐患和 C 比较器的溢出问题比对着样例 debug 高效太多。如果这是你的第一道多语言计数题我建议先别看代码自己用纸笔把 [1,1,2,2,3,4,4,5,5]、target6 这个例子手算一遍正确结果是 6 个元组然后用至少三种语言提交。等四个版本全部跑通你对排序、双指针、组合计数和语言特性的理解会上一个台阶。这份新卷的 100 分拿得不亏。