有效三角形的个数一道必刷的经典题“面试必看有效三角形的个数”这标题我信一半。真正面试过的人心里都有数面热点题这事儿既考刷题量也考讲题的逻辑。但“有效三角形的个数”这一道属于那种看似数学、实则是纯双指针套路的题它不考你三角不等式推得多深考的是你能不能看穿排序后指数规模降维的那一下。我见过太多人卡在“为什么 right-- 就能把计数一次拉平”这个点上讲不利索就挂。这篇文章把这道题从题目分析、暴力思路、优化推导到双指针具体实现、边界陷阱、面试追问应付方案全部摊开讲一遍。适合所有准备算法面试、尤其近期在刷“数组 双指针”专项的读者。你说它是刷题笔记也好说它是面试押题准备也罢读完你至少能自信地把这道题从头推到尾而不是只背个模板。1. 从题干推导出最优解法1.1 题目到底在问什么先看原题描述通常是这样给定一个包含非负整数的数组你的任务是统计其中可以组成三角形三条边的三元组个数。也就是从数组里任选三个数看能不能构成一个有效三角形。所谓“有效”就是三条边满足任意两边之和大于第三边等价于短边之和大于长边。这里有三个隐藏条件容易让人跑偏。第一数组长度可能很大记得最狠的情况是 n 到 2000 左右暴力三层循环铁定超时。第二元素是非负整数0 的存在是个坑因为 0 不能作为三角形边后续计数要以“大于”而不是“大于等于”为准。第三数字可能有重复而且下标不同就算不同三元组这在题目里常常被忽略。比如[2, 2, 3]只能算 1 个有效组合但[2, 2, 3, 3]就有 4 种组合因为两个 2 和两个 3 各自有下标差异。我在一开始刷这道题时就踩过一次命名上的坑总想把它当成几何题来解琢磨海伦公式、余弦定理之类的。后来才明白这道题考察的第一层是“排序思想”第二层是“单调性 双指针”第三层是“计数去重”。本质上它是一个组合计数问题不是几何问题。1.2 为什么暴力解法不是真的解法如果你刚拿到题会想到什么最自然的思路就是三重循环枚举所有三元组再判断是否满足a b c。复杂度 O(n^3)n 一到 1000 就基本跑不动。LeetCode 上 n 可以明确给你 1000 甚至 2000O(n^3) 是亿级甚至十亿级的操作显然不是面试官想要的标准答案。但是暴力解法不是没有价值。它的价值在于确认你对判断条件的理解是否正确。我在实际讲题时经常会用暴力解法来做“基准测试”用一个几千量级的小数组跑一次拿正确结果跟双指针解法结果对拍。没有这个基准我后面优化出错了都找不到原因。如果你去问面试官“暴力行不行”他不会直接否定你但你要自己很快反应过来如果 n 是 1000暴力三层循环实际上要做 1.67 亿次判断在 1 秒的时限内跑 C 可能将将过换成 Python 就铁定超时。面试官真正想听的是如何在 O(n^2) 或者 O(n^2 log n) 的复杂度内解决。1.3 排序是这道题唯一的朴素直觉排序为什么是这里正确的第一步原因是你希望快速判断三条边能否组成三角形时最怕的是要考虑三条边之间的大小关系。如果先排序从小到大排好之后对于任意三条边a[i]、a[j]、a[k]只要 i j k那么它们天然满足a[i] a[k] a[j]和a[j] a[k] a[i]因为最长边是 a[k]另外两边之和一定大于它吗不对你还需要验证a[i] a[j] a[k]。排序最大的好处是把“无序三元组”的问题变成“有序三元组”的问题。你只需要关心最大的那条边。这就是三角不等式从三个都要判断变成了只要判断一个两个较小边之和是否大于最大边。这个想法其实生活中就有对应。三个人搭帐篷三根支架长度差得离谱你一眼就能看出其中一根太长另两根加起来都够不着它那就不用再去量另外两个方向的比较了。排序就是帮你把“最长的那根”拎出来。一旦完成了第一步排序你之后所有的优化都在“已经有序”这个前提下展开问题立刻从几何变成“找两个数的和大于某个数”。2. 双指针解法的原理与推导过程2.1 固定最长边后问题变成了什么最优雅的解法思路是以最长边为锚点也就是从数组末尾开始一个一个固定所谓的a[k]然后看在这个最长边之前的所有数中有多少对(a[i], a[j])满足a[i] a[j] a[k]。这其实等同于“两数之和大于目标值”的问题。暴力一点固定 k 后再用两层循环枚举 i 和 j复杂度就变成 O(n^2) 的常数倍。操作上没毛病但面试评分不会给你满分因为还需要往前一步利用有序性把内层的双循环压成单循环。先写出这个子问题的暴力逻辑对于固定的 k令 i 从 0 开始j 从 k-1 开始双指针向内移动如果发现a[i] a[j] a[k]就说明从 i 到 j-1 的所有数跟 a[j] 组合都能满足条件因为 i 到 j-1 都比 a[i] 大或相等所以计数直接加j - i然后 j 左移。否则说明 a[i] 太短了跟最长的 a[j] 配合都不够那就 i 右移。这里选j从k-1而不是从i1开始是我当初学这道题时最容易想不通的点。要解释清楚因为两个数从两端逼近中间时能利用“右端最大”这个信息一旦右端加上当前左端已经大于目标那么当前左端到右端之间的所有数跟右端配对一定都满足条件。如果你从 i1 开始从左往右扫那么你需要一个个试探 j 往右延伸到哪里才停止无法实现一次跳多个计数。2.2 双指针单调性到底体现在哪里双指针解法的正确性根源在于两个指针移动过程中“单调性”的保持。你要意识到当你固定a[k]后a[i]在增大a[j]在减小。每轮循环如果a[i] a[j] a[k]那么所有a[i1]到a[j-1]与a[j]配对都必然满足条件吗不一定因为 a[i1] 比 a[i] 更大所以a[i1] a[j] a[k]一定成立。这句话是对的因为加数变大了和只会变大。反过来如果a[i] a[j] a[k]说明当前的 a[i] 太小了就算配上目前最大的 a[j] 也不够。那更小的左端值就更不可能够。所以此时唯一的选择是让 i 向右移动换一个更大的 a[i]。这个“其中一个指针移动后另一个指针的可行区间只会单向变化”的特性就是双指针能在线性时间内完成计数的一整套逻辑。它比二分还难想一点因为你要理解“为什么不需要回溯”。左指针做过的事情右指针不会回到过去重新检查因为问题域的单调性保证了不会漏解。拿真实数据举例数组[1, 2, 3, 4, 5]固定 k 指向 5i 指向 1j 指向 41 4 5不成立所以 i 移到 22 4 5成立于是计数加j - i也就是4 - 2 2代表 (2,4) 和 (3,4) 两对都满足然后 j 移到 3接着2 3 5不成立i 移到 3此时 i j 退出。这个过程一共移动了 4 次指针计数出 2 对全靠“一次跳多对”的计数技巧复杂度才能压到 O(n)。2.3 复杂度分析不是背答案这道题的复杂度分析你必须能自己推导出来。排序用 O(n log n)这是标准排序的时间。接下来外层循环固定 kk 从 2 跑到 n-1内层双指针从 (0, k-1) 开始往中间靠总共最多移动 n 次。为什么内层是 O(n)因为 i 和 j 都是单向移动i 总共最多向右移动 k 次j 总共最多向左移动 k 次加起来最多移动 2k 次取 O(k)外层再循环 n 次所以整体是 O(n^2)。空间复杂度这里也非常讨喜排序一般用原地排序额外空间 O(1)不需要开二维数组。遇到这种题面试官通常会顺着复杂度往下问如果数组是无序的呢那排序的 O(n log n) 无法避免。如果数组里全是负数呢那需要处理绝对值问题但题目给了非负整数的约束这道题就不需要考虑。如果让你用哈希表来优化你能做吗事实上很难因为这是三元组组合计数问题哈希表处理两数之和还行处理“大于”这种不等关系反而不如排序 双指针来得直接。所以这道题的正确思路链是排序 → 固定最长边 → 双指针计数。理解了每一步为什么是必要的你才算真的掌握。3. 手把手写好双指针代码避开那几个经典坑3.1 回到代码细节才是魔鬼我现在给出一个清晰、可复现的 Python 解法。之所以用 Python是因为面试时写起来快而且表达逻辑直观。如果你用 C 或 Java思路完全一样注意下标边界就行。def triangleNumber(nums): nums.sort() n len(nums) ans 0 for k in range(n - 1, 1, -1): i 0 j k - 1 while i j: if nums[i] nums[j] nums[k]: ans j - i j - 1 else: i 1 return ans这段代码短但每个细节都值得掰开揉碎讲。第一range(n - 1, 1, -1)是从数组尾部往前遍历最长边。为什么从 n-1 开始为什么到 1 结束因为至少要留两个数作为短边k 最小是 2。这里如果你写range(n - 1, 1, -1)Python 会自动停在 2因为 range 不包含右端点 2这是你的 k 最后取到的值是 2。如果你写range(n - 1, 0, -1)那 k1 时 i0、j0循环根本不入口白跑一次。第二内层双指针i从 0 开始j从k-1开始。这里有个常见误解是 i 从 0 开始会不会漏掉一些组合不会。因为你的 k 是全局最长边所有短边都在它左边。从数组最左端开始往右移动等价于枚举所有可能的较小边。你只关心相对位置不关心绝对下标所以从 0 开始是最自然的选择。第三计数逻辑里那句ans j - i是全文最关键的一行。它的意思是当nums[i] nums[j] nums[k]成立时对于当前固定的 j任何下标在[i, j-1]之间的数跟 nums[j] 组合都满足条件。因为数组有序nums[i]是当前可行的最小左端值比它大的左边所有值配合当前右端都一定满足不等式。所以不需要一个一个试直接加 j - i 个。这个跳步就是 O(n^3) 到 O(n^2) 的关键。第四当你加完计数后为什么是j - 1而不是i 1因为当前 a[j] 已经跟左边所有可能的值都比较过了所有以 a[j] 为最大短边的有效组合都已经计数完毕。j 可以安全地向左移动。反过来如果不满足条件说明当前 a[i] 太小所有以 a[i] 为最小短边的组合都不可能有效所以 i 向右移动。每次面试讲到这一行我都会补一句如果你把j - 1和i 1搞反计数就会出现重复或遗漏而且代码在某些输入下还能跑出正确结果让你稀里糊涂地错下去。这种“侥幸正确”的 bug 最可怕面试官一眼就能看出你没有真正理解代码。3.2 为什么ans j - i不是ans 1这四个字符的差距直接决定了你是 O(n^2) 还是 O(n^3)。我来做一个具体的推演假设数组是[3, 4, 5, 6, 7]固定 k 指向 7那么 i 从 3 开始j 从 6 开始。第一轮3 6 7成立。此时如果你只ans 1那你就漏掉了(4,6)、(5,6)这两对。因为 4、5 都比 3 大跟 6 配也都大于 7。j - 1后j 指向 5此时3 5 7成立你再ans 1只加进(3,5)。这样最终只统计了 2 个组合而真实有效的短边组合有(3,6)、(4,6)、(5,6)、(3,5)、(4,5)这 5 个。漏了 3 个。这就是只加 1 的代价。如果正确使用ans j - i第一轮就加3代表 (3,6)、(4,6)、(5,6)第二轮加1代表 (3,5)第三轮3 4 7不成立i 右移4 4 7此时 i3、j3循环退出。总计数是 4等等好像还少了一个 (4,5)。让我重新模拟一遍。数组[3, 4, 5, 6, 7]k 指向 7。i0 (值3)j3 (值6)。367成立ans3代表组合(3,6)、(4,6)、(5,6)j 左移到值 5下标2。此时 i0 (3)j2 (5)。357成立ans2代表组合(3,5)、(4,5)j 左移到值 4下标1。此时 i0 (3)j1 (4)。347不成立i 右移到下标1。i1 (4)j1 (4)i j退出。总计 ans5。完美。这里我一开始误算了 j 的当前位置实际上 j 移动一次后是值 5 而不是 4。整个过程说明如果你在纸上模拟时小心下标就不会出这种偏差。面试时如果你的思路不清纸面模拟一定是乱套的。所以你可以记一个记忆口诀满足条件右指针左移一次性收割 j-i 个不满足条件左指针右移继续尝试变大。这两个方向本身就是双指针题目里最常见的“左右互搏”套路跟“两数之和”系列是同一个味道。3.3 再补一个二分查找版本用作对比虽然双指针是这道题的最优解但你最好也了解一下二分的做法因为面试官可能会故意引导你往二分上想。固定 k 和 j 的思路对于每个 k枚举 j 从 k-1 往左然后用二分查找找到第一个满足与 a[j] 之和大于 a[k] 的位置。设这个位置是 idx那么从 idx 到 j-1 之间的所有数都能跟 a[j] 形成有效组合计数加j - idx。def triangleNumber_binary(nums): nums.sort() n len(nums) ans 0 for k in range(n - 1, 1, -1): for j in range(k - 1, 0, -1): target nums[k] - nums[j] idx bisect_right(nums, target, 0, j) ans j - idx return ans这个版本复杂度是 O(n^2 log n)因为外层 k 是 O(n)内层 j 是 O(n)每次二分是 O(log n)。在 n2000 时仍然可行但比双指针 O(n^2) 差了一个 log 因子。面试里你提这个方案等于告诉面试官你掌握多种思路但最终收敛到双指针是被复杂度说服的。不过要小心bisect_right找的是第一个大于 target 的下标也就是最小满足a[i] a[j] a[k]的 i。因为数组是有序的所有下标大于 idx 且小于 j 的数都满足条件所以计数j - idx。这个理解如果不到位很容易把bisect_left和bisect_right用错。3.4 关于 0 值的那个坑题目说了非负整数那么数组里可能有 0。0 能不能作为三角形边不能因为 0 x x不可能严格大于第三边。这个数学事实在排序后依然成立但双指针计数时会不会把 0 也算进去答案是会除非你加边界判断。举例数组[0, 1, 2, 3]固定 k 指向 3。i0值0j2值2023不成立i 右移i1值1123不成立i 右移循环退出。这个过程中 0 没有产生有效计数因为条件不满足时我们直接 i 了不会错误累计。所以 0 值在这套逻辑下天然被排除了你不需要特判。这个结论值得你在面试时说一嘴免得面试官觉得你没注意到边界的坑。但如果数组里全是 0外层 k 和 j 移动过程中000永远为假ans 保持 0返回正确结果。实测下来这套双指针写法不需要对 0 做额外判断是因为不等式严格大于从数学层面直接过滤掉了 0。3.5 边界 case 这几组测试必须跑不管笔试还是面试写完代码第一反应应该是拿边界 case 测一遍。我列一组自测列表建议你收藏[0, 0, 0]没有三角形输出 0。[1, 1, 1]一个等边三角形输出 1。[1, 2, 3]123不严格大于输出 0。[1, 2, 3, 4]有效组合只有[2,3,4]输出 1。[4, 4, 4, 4]任选三个都有效输出 C(4,3)4。[3, 4, 5, 6, 7]按上面推算是 5你可以手算验证。这些边界 case 不仅是用来验证正确性也是面试现场展示严谨性的道具。你千万不要写完代码就说“完了”要主动跟面试官说“我跑几个边界测试”。这一下就能从普通候选人里跳出来。4. 面试官最喜欢追问的变体和延伸问题4.1 如果只要求判断是否存在而不是计数这个变体题目是给定一个数组判断是否存在任意三条边可以组成三角形。这个问题比计数简单得多排序后只需要检查相邻的三个数。为什么如果你排序后从小到大找一定能组成三角形的三元组一定会在某个连续三个数中出现。你可以这样跟面试官推理假设存在a[i] a[j] a[k]满足a[i] a[j] a[k]那么在排序数组中a[j-1] a[i] a[j-1] a[j]所以a[j-1] a[j] a[j1]是否一定成立不一定因为 a[j1] 可能不等于 a[k]。严谨推导是如果a[i] a[j] a[k]则a[j] a[j] a[k]不一定成立但a[k-2] a[k-1] a[i] a[j]这里需要更仔细。实际上有一个广为人知的结论排序后如果存在任何有效三元组则一定存在连续三个数构成有效三元组。假设一个有效三元组是a[i] a[j] a[k]且它们不连续。因为 a[j-1] 介于 a[i] 与 a[j] 之间所以 a[j-1] a[i]因此 a[j-1] a[j] a[j] a[i] a[k]不对a[j-1] a[j] a[i] a[j] a[k]所以a[j-1] a[j] a[k]也成立。但 a[k] 可能比 a[j1] 大所以不能直接说连续三个。不过可以一路向左替换最终能得到连续三个数吗如果 a[k] 和 a[j] 之间还有空隙a[j1] 大于 a[j]那么 a[j-1] a[j] a[k] 并不能推导出大于 a[j1]。可以构造反例比如[2, 3, 4, 100]存在 (2,3,4)连续三个就是它本身。但如果存在的是 (2,3,100) 呢32 100 不成立。所以更稳妥的说法是判断存在性排序后仍然用双指针 O(n^2) 解决或者更简单点固定 k 后二分查找第一个合适的位置判断是否存在就行。不要一口咬定“只需检查连续三个数”除非你确认结论成立。我实测下来连续三个数的结论不严谨但很多简单题解里直接用因为对于满足条件的三元组可以找到某种相邻的三个数替换。最保险的答复是排序后从最大边开始扫对于每个 k如果存在某两个数的和大于 a[k]则存在这一样可以用双指针判断但没必要计数找到直接返回 True。复杂度也是 O(n^2)不过通常实际执行时会提前终止。这道变体的意义就是帮你理解“计数”和“判断存在”的差别面试官从计数题往下问一层就是看你有没有吃透双指针的提前退出逻辑。4.2 如果用哈希表能解决吗这题能不能用哈希表优化到 O(n^2) 以下我直接说结论不能。至少我没有找到能稳定优于 O(n^2) 的哈希表方案。原因很简单你不能枚举三元组的情况下无法利用哈希表快速判断“两数之和大于第三边”因为这是不等关系不是相等关系。哈希表擅长精确匹配不擅长范围统计。如果你非要往哈希表上靠可以这样处理固定两条边 a 和 b然后需要统计有多少 c 小于 ab。这需要在排序数组上做二分或指针移动本质上还是离不开有序性。哈希表存值对应的计数可以帮你跳过重复值的遍历但最坏情况仍然是 O(n^2)。面试时说这个思路可以体现你对数据结构的边界认识。我之前试过一个骚操作把数组所有两两和放进哈希表再枚举第三边查表结果发现空间直接爆掉n2000 时两两和就是 200 万级别存下去不仅浪费内存查询也不比双指针快。这种方案只适合 n 很小的情况面试提出来当反面教材还挺有意思。4.3 大数场景下溢出问题要不要考虑当数组元素很大接近 2^31-1 时两个数相加可能超过 int 的范围。在 C 里这就可能触发有符号整数溢出行为未定义。面试官如果问到这个点你要能接住用 long long 类型接收两数之和或者在比较前做变换比如把a b c转换成a c - b这样避免加法溢出。这个细节在 Python 里不存在因为 Python 的 int 是任意精度。但如果岗位要求 C/Java面试官一定会挖这个坑。我记得有一次模拟面试候选人写 C 循环里直接if (nums[i] nums[j] nums[k])我追问“如果 nums[i] 是 INT_MAX 呢”他愣了几秒才反应过来。这个细节虽然不影响算法主框架但是代码是否稳健的分水岭。标准规避写法是if (nums[i] nums[k] - nums[j])因为nums[k] - nums[j]一定不会溢出两个非负数相减结果范围是[-2^311, 2^31-1]安全。这比转 long long 更高效也更能体现经验。4.4 大规模数据下能更快吗n2000 时 O(n^2) 很轻松但如果 n 到 10^5 甚至 10^6双指针也顶不住。这时候就需要更有创意的思路。一个可讨论的方向是如果元素值域有限比如所有数字都在 0~100000 范围你可以用值域上的“前缀和 枚举两条边”来做但这本质上还是 O(n^2)只不过把 n 换成值域。另一个方向是分治把数组分成两半递归统计各自内部的三角形再统计跨两半的组合。跨两半的组合需要更复杂的分类讨论实现难度高面试一般不会考到 n10^5 的版本。你只要知道 O(n^2) 已经是这道题在一般约束下的最优解就行。面试官问“还能更快吗”其实就是看你是否理解复杂度边界。你可以诚实回答在基于比较的排序 枚举模型下O(n^2) 是已知最优想要突破需要值域约束或额外数据结构但通常不是这道题的目的。5. 从表达到复盘一道题暴露的算法功底5.1 如何在面试现场讲好这道题题目本身不难难的是你能不能在一个小时内把思路讲得让面试官点头。我建议你按照“暴力 → 排序优化 → 双指针 → 复杂度分析”这条线来讲不要一上来就甩双指针。这样做的原因是面试官想看到的是你的推导过程而不是记忆力。我常用的讲述顺序是“先排序因为排序后能确定大小关系只需要验证短边和大于最长边。”“固定最长边 k问题变成在 k 左侧找多少对 (i, j) 满足两数之和大于 nums[k]。”“如果暴力枚举所有 i、j那就是 O(n^2)再套 k 的循环就是 O(n^3)。这里可以利用有序性用双指针一次性数完。”“具体来说i 从最左端开始j 从 k-1 开始。如果 nums[i] nums[j] nums[k]说明 i 到 j-1 之间所有数都满足条件计数加 j - i然后 j 左移否则 i 右移。”“每个 k 内 i 和 j 总共最多移动 n 次所以整体 O(n^2)排序 O(n log n)空间 O(1)。”这五句话能覆盖算法正确性、复杂度、实现关键足够撑起一道中等难度题。有一个练习方法是自己给自己讲一遍录音然后回放。如果你发现卡壳或者需要“嗯……然后……”来过渡说明你还没有完全吃透双指针为什么能跳过这么多组合。真实面试时紧张会放大这些不流畅所以建议提前口头演练三遍以上。5.2 常见翻车行为现场会挂的那种我以面试官视角列几个常见雷区上来就写代码跳过思路沟通。哪怕写对了面试官会认为你背题追问细节容易垮。排序后直接两层循环固定 i 和 j然后二分找 k这是 O(n^2 log n)虽然对但不如双指针面试官觉得你差一点意思。忘了包含重复下标。比如[1, 1, 2]应该返回 0但有些人枚举时把两个 1 当成不同下标导致计数错误。这题重复元素下标不同是算不同三元组的所以[2, 2, 3]只能算 1而[2, 2, 3, 3]算 4 个你不能去重。边界条件处理错最常见的就是 k 的起始位置写成 n-1 而 j 从 k 开始直接把最长边自己跟自己比较产生错误计数。我在实际做模拟面试时发现写对的人往往能说出每一行意图写错的人大多卡在“j 移动方向”和“ans j - i”这两个地方。你把这两个点研究透这道题基本就拿下了。5.3 从一道题看双指针的家族体系“有效三角形的个数”不是孤立的题目它跟“三数之和”、“最接近的三数之和”、“四数之和”都属于同一个家族固定一个指针另外两个指针内收。掌握了这道题你再去做“两数之和 II - 输入有序数组”会非常顺因为双指针在有序数组上处理“和等于目标”就是左右夹逼的弱化版。我建议你刷完这道题后花半小时把这几道题连起来过一遍LeetCode 167两数之和 II有序数组目标值精确匹配。LeetCode 15三数之和排序后固定一个数剩下两个双指针。LeetCode 16最接近的三数之和双指针加一个全局最优值更新。LeetCode 18四数之和多套一层循环。这些题共用同一个框架你只需要调整判断条件和计数方式。做过几道之后你会对“排序 双指针”这个组合产生肌肉记忆面试时审题速度都会快很多。6. 我实测踩过的坑和一些经验总结6.1 先讲一个我真实的翻车经历有一次我在本地练习时写了一个版本自测全过结果提交到 LeetCode 直接超时。排查了半天发现我把内层循环写成了for j in range(k-1, 0, -1)而 i 在循环内每次都重新初始化为0。这就导致每一层 j 都重新遍历一次左侧全部元素复杂度退化成 O(n^3)。这个坑特别容易踩尤其是从“固定 j 找 i”的二分思路切换过来时。双指针的核心就是 i 和 j 同时维护、各自单向移动绝不能在 j 循环内外重新初始化 i。那次之后我总结出一个规则一旦你在内层循环里发现某个指针被反复重置就要警惕复杂度退化。还有一次我在写二分版本时用bisect_left找满足条件的最小 i结果发现漏掉了很多组合。分析原因是我要找的是a[i] target的第一个位置应该用bisect_right因为 target 本身如果等于某个数组值它是不能算作有效组合的需要严格大于。这种边界如果不跑测试真的很难发现。6.2 纸上模拟是学好双指针最有效的方式如果你觉得双指针的逻辑绕我强烈建议你拿一张纸把[3, 4, 5, 6, 7]这个案例按我上面的推演手写几遍每一步写下 i、j、k 的数字和 ans 的变化。这个过程花不到五分钟但能让你彻底看清“为什么一次加 j-i 个”。我在学习阶段就是把这道题手推了四五遍后来遇到类似的“乘积小于 K 的子数组”等题目也都用同样的纸面推演法消化。其实双指针很多题的“一次性收割”本质都是一样的当你发现一个窗口满足条件时窗口内每一个位置都是合法答案于是整体计数而不是逐个枚举。你把这个思维模式固化下来以后碰到任何“子数组计数”或“配对计数”问题都会很有感觉。6.3 这道题在面试中的隐藏加分点除了算法正确下面几个小点能在面试中给你加分主动说边界测试提到0值和重复值。这说明你有测试意识不只是写代码。主动分析溢出风险把a b c改写成a c - b。这在大厂面试里很讨喜因为工程上溢出问题特别常见。主动提二分版本做对比说明你不止会一种解法有比较和权衡的意识。在复杂度分析时解释排序后双指针的单调性来源而不是背诵结论。这几条不一定每场面试都能用上但只要有机会尽量自然地展示不要让面试官觉得你在“背包装”。6.4 如果时间有限这道题怎么速成如果你离面试只剩几天来不及系统刷题我建议你就盯着这道题以及它的三个变体两数之和 II、三数之和、乘积小于 K 的子数组。这四个题能覆盖大部分双指针计数的套路。每天花 20 分钟把这道题的思路链默写一遍排序 → 固定最长边 → 双指针内收 → 计数跳步。当你到了考场哪怕遇到变体也能迅速反应到“是不是双指针可解”。其实大多数中等难度的数组题面试官的预期就是你能想到排序 双指针这个组合代码写不写得完全漂亮反而是次要的。我个人在实际操作中的体会是双指针题最怕的不是想不到而是想到了说不清。所以你在家练习时不要闷头刷题试着像给人讲课一样把每次解题思路讲出来讲得越多面试时越稳。这道“有效三角形的个数”如果能在五分钟内边讲边写完整你的双指针这一关基本就算过了。 
长河君 · 2026/10/7 2:23:25 · 阅读 1.2k 有效三角形的个数：排序+双指针面试经典题深度解析
有效三角形的个数一道必刷的经典题“面试必看有效三角形的个数”这标题我信一半。真正面试过的人心里都有数面热点题这事儿既考刷题量也考讲题的逻辑。但“有效三角形的个数”这一道属于那种看似数学、实则是纯双指针套路的题它不考你三角不等式推得多深考的是你能不能看穿排序后指数规模降维的那一下。我见过太多人卡在“为什么 right-- 就能把计数一次拉平”这个点上讲不利索就挂。这篇文章把这道题从题目分析、暴力思路、优化推导到双指针具体实现、边界陷阱、面试追问应付方案全部摊开讲一遍。适合所有准备算法面试、尤其近期在刷“数组 双指针”专项的读者。你说它是刷题笔记也好说它是面试押题准备也罢读完你至少能自信地把这道题从头推到尾而不是只背个模板。1. 从题干推导出最优解法1.1 题目到底在问什么先看原题描述通常是这样给定一个包含非负整数的数组你的任务是统计其中可以组成三角形三条边的三元组个数。也就是从数组里任选三个数看能不能构成一个有效三角形。所谓“有效”就是三条边满足任意两边之和大于第三边等价于短边之和大于长边。这里有三个隐藏条件容易让人跑偏。第一数组长度可能很大记得最狠的情况是 n 到 2000 左右暴力三层循环铁定超时。第二元素是非负整数0 的存在是个坑因为 0 不能作为三角形边后续计数要以“大于”而不是“大于等于”为准。第三数字可能有重复而且下标不同就算不同三元组这在题目里常常被忽略。比如[2, 2, 3]只能算 1 个有效组合但[2, 2, 3, 3]就有 4 种组合因为两个 2 和两个 3 各自有下标差异。我在一开始刷这道题时就踩过一次命名上的坑总想把它当成几何题来解琢磨海伦公式、余弦定理之类的。后来才明白这道题考察的第一层是“排序思想”第二层是“单调性 双指针”第三层是“计数去重”。本质上它是一个组合计数问题不是几何问题。1.2 为什么暴力解法不是真的解法如果你刚拿到题会想到什么最自然的思路就是三重循环枚举所有三元组再判断是否满足a b c。复杂度 O(n^3)n 一到 1000 就基本跑不动。LeetCode 上 n 可以明确给你 1000 甚至 2000O(n^3) 是亿级甚至十亿级的操作显然不是面试官想要的标准答案。但是暴力解法不是没有价值。它的价值在于确认你对判断条件的理解是否正确。我在实际讲题时经常会用暴力解法来做“基准测试”用一个几千量级的小数组跑一次拿正确结果跟双指针解法结果对拍。没有这个基准我后面优化出错了都找不到原因。如果你去问面试官“暴力行不行”他不会直接否定你但你要自己很快反应过来如果 n 是 1000暴力三层循环实际上要做 1.67 亿次判断在 1 秒的时限内跑 C 可能将将过换成 Python 就铁定超时。面试官真正想听的是如何在 O(n^2) 或者 O(n^2 log n) 的复杂度内解决。1.3 排序是这道题唯一的朴素直觉排序为什么是这里正确的第一步原因是你希望快速判断三条边能否组成三角形时最怕的是要考虑三条边之间的大小关系。如果先排序从小到大排好之后对于任意三条边a[i]、a[j]、a[k]只要 i j k那么它们天然满足a[i] a[k] a[j]和a[j] a[k] a[i]因为最长边是 a[k]另外两边之和一定大于它吗不对你还需要验证a[i] a[j] a[k]。排序最大的好处是把“无序三元组”的问题变成“有序三元组”的问题。你只需要关心最大的那条边。这就是三角不等式从三个都要判断变成了只要判断一个两个较小边之和是否大于最大边。这个想法其实生活中就有对应。三个人搭帐篷三根支架长度差得离谱你一眼就能看出其中一根太长另两根加起来都够不着它那就不用再去量另外两个方向的比较了。排序就是帮你把“最长的那根”拎出来。一旦完成了第一步排序你之后所有的优化都在“已经有序”这个前提下展开问题立刻从几何变成“找两个数的和大于某个数”。2. 双指针解法的原理与推导过程2.1 固定最长边后问题变成了什么最优雅的解法思路是以最长边为锚点也就是从数组末尾开始一个一个固定所谓的a[k]然后看在这个最长边之前的所有数中有多少对(a[i], a[j])满足a[i] a[j] a[k]。这其实等同于“两数之和大于目标值”的问题。暴力一点固定 k 后再用两层循环枚举 i 和 j复杂度就变成 O(n^2) 的常数倍。操作上没毛病但面试评分不会给你满分因为还需要往前一步利用有序性把内层的双循环压成单循环。先写出这个子问题的暴力逻辑对于固定的 k令 i 从 0 开始j 从 k-1 开始双指针向内移动如果发现a[i] a[j] a[k]就说明从 i 到 j-1 的所有数跟 a[j] 组合都能满足条件因为 i 到 j-1 都比 a[i] 大或相等所以计数直接加j - i然后 j 左移。否则说明 a[i] 太短了跟最长的 a[j] 配合都不够那就 i 右移。这里选j从k-1而不是从i1开始是我当初学这道题时最容易想不通的点。要解释清楚因为两个数从两端逼近中间时能利用“右端最大”这个信息一旦右端加上当前左端已经大于目标那么当前左端到右端之间的所有数跟右端配对一定都满足条件。如果你从 i1 开始从左往右扫那么你需要一个个试探 j 往右延伸到哪里才停止无法实现一次跳多个计数。2.2 双指针单调性到底体现在哪里双指针解法的正确性根源在于两个指针移动过程中“单调性”的保持。你要意识到当你固定a[k]后a[i]在增大a[j]在减小。每轮循环如果a[i] a[j] a[k]那么所有a[i1]到a[j-1]与a[j]配对都必然满足条件吗不一定因为 a[i1] 比 a[i] 更大所以a[i1] a[j] a[k]一定成立。这句话是对的因为加数变大了和只会变大。反过来如果a[i] a[j] a[k]说明当前的 a[i] 太小了就算配上目前最大的 a[j] 也不够。那更小的左端值就更不可能够。所以此时唯一的选择是让 i 向右移动换一个更大的 a[i]。这个“其中一个指针移动后另一个指针的可行区间只会单向变化”的特性就是双指针能在线性时间内完成计数的一整套逻辑。它比二分还难想一点因为你要理解“为什么不需要回溯”。左指针做过的事情右指针不会回到过去重新检查因为问题域的单调性保证了不会漏解。拿真实数据举例数组[1, 2, 3, 4, 5]固定 k 指向 5i 指向 1j 指向 41 4 5不成立所以 i 移到 22 4 5成立于是计数加j - i也就是4 - 2 2代表 (2,4) 和 (3,4) 两对都满足然后 j 移到 3接着2 3 5不成立i 移到 3此时 i j 退出。这个过程一共移动了 4 次指针计数出 2 对全靠“一次跳多对”的计数技巧复杂度才能压到 O(n)。2.3 复杂度分析不是背答案这道题的复杂度分析你必须能自己推导出来。排序用 O(n log n)这是标准排序的时间。接下来外层循环固定 kk 从 2 跑到 n-1内层双指针从 (0, k-1) 开始往中间靠总共最多移动 n 次。为什么内层是 O(n)因为 i 和 j 都是单向移动i 总共最多向右移动 k 次j 总共最多向左移动 k 次加起来最多移动 2k 次取 O(k)外层再循环 n 次所以整体是 O(n^2)。空间复杂度这里也非常讨喜排序一般用原地排序额外空间 O(1)不需要开二维数组。遇到这种题面试官通常会顺着复杂度往下问如果数组是无序的呢那排序的 O(n log n) 无法避免。如果数组里全是负数呢那需要处理绝对值问题但题目给了非负整数的约束这道题就不需要考虑。如果让你用哈希表来优化你能做吗事实上很难因为这是三元组组合计数问题哈希表处理两数之和还行处理“大于”这种不等关系反而不如排序 双指针来得直接。所以这道题的正确思路链是排序 → 固定最长边 → 双指针计数。理解了每一步为什么是必要的你才算真的掌握。3. 手把手写好双指针代码避开那几个经典坑3.1 回到代码细节才是魔鬼我现在给出一个清晰、可复现的 Python 解法。之所以用 Python是因为面试时写起来快而且表达逻辑直观。如果你用 C 或 Java思路完全一样注意下标边界就行。def triangleNumber(nums): nums.sort() n len(nums) ans 0 for k in range(n - 1, 1, -1): i 0 j k - 1 while i j: if nums[i] nums[j] nums[k]: ans j - i j - 1 else: i 1 return ans这段代码短但每个细节都值得掰开揉碎讲。第一range(n - 1, 1, -1)是从数组尾部往前遍历最长边。为什么从 n-1 开始为什么到 1 结束因为至少要留两个数作为短边k 最小是 2。这里如果你写range(n - 1, 1, -1)Python 会自动停在 2因为 range 不包含右端点 2这是你的 k 最后取到的值是 2。如果你写range(n - 1, 0, -1)那 k1 时 i0、j0循环根本不入口白跑一次。第二内层双指针i从 0 开始j从k-1开始。这里有个常见误解是 i 从 0 开始会不会漏掉一些组合不会。因为你的 k 是全局最长边所有短边都在它左边。从数组最左端开始往右移动等价于枚举所有可能的较小边。你只关心相对位置不关心绝对下标所以从 0 开始是最自然的选择。第三计数逻辑里那句ans j - i是全文最关键的一行。它的意思是当nums[i] nums[j] nums[k]成立时对于当前固定的 j任何下标在[i, j-1]之间的数跟 nums[j] 组合都满足条件。因为数组有序nums[i]是当前可行的最小左端值比它大的左边所有值配合当前右端都一定满足不等式。所以不需要一个一个试直接加 j - i 个。这个跳步就是 O(n^3) 到 O(n^2) 的关键。第四当你加完计数后为什么是j - 1而不是i 1因为当前 a[j] 已经跟左边所有可能的值都比较过了所有以 a[j] 为最大短边的有效组合都已经计数完毕。j 可以安全地向左移动。反过来如果不满足条件说明当前 a[i] 太小所有以 a[i] 为最小短边的组合都不可能有效所以 i 向右移动。每次面试讲到这一行我都会补一句如果你把j - 1和i 1搞反计数就会出现重复或遗漏而且代码在某些输入下还能跑出正确结果让你稀里糊涂地错下去。这种“侥幸正确”的 bug 最可怕面试官一眼就能看出你没有真正理解代码。3.2 为什么ans j - i不是ans 1这四个字符的差距直接决定了你是 O(n^2) 还是 O(n^3)。我来做一个具体的推演假设数组是[3, 4, 5, 6, 7]固定 k 指向 7那么 i 从 3 开始j 从 6 开始。第一轮3 6 7成立。此时如果你只ans 1那你就漏掉了(4,6)、(5,6)这两对。因为 4、5 都比 3 大跟 6 配也都大于 7。j - 1后j 指向 5此时3 5 7成立你再ans 1只加进(3,5)。这样最终只统计了 2 个组合而真实有效的短边组合有(3,6)、(4,6)、(5,6)、(3,5)、(4,5)这 5 个。漏了 3 个。这就是只加 1 的代价。如果正确使用ans j - i第一轮就加3代表 (3,6)、(4,6)、(5,6)第二轮加1代表 (3,5)第三轮3 4 7不成立i 右移4 4 7此时 i3、j3循环退出。总计数是 4等等好像还少了一个 (4,5)。让我重新模拟一遍。数组[3, 4, 5, 6, 7]k 指向 7。i0 (值3)j3 (值6)。367成立ans3代表组合(3,6)、(4,6)、(5,6)j 左移到值 5下标2。此时 i0 (3)j2 (5)。357成立ans2代表组合(3,5)、(4,5)j 左移到值 4下标1。此时 i0 (3)j1 (4)。347不成立i 右移到下标1。i1 (4)j1 (4)i j退出。总计 ans5。完美。这里我一开始误算了 j 的当前位置实际上 j 移动一次后是值 5 而不是 4。整个过程说明如果你在纸上模拟时小心下标就不会出这种偏差。面试时如果你的思路不清纸面模拟一定是乱套的。所以你可以记一个记忆口诀满足条件右指针左移一次性收割 j-i 个不满足条件左指针右移继续尝试变大。这两个方向本身就是双指针题目里最常见的“左右互搏”套路跟“两数之和”系列是同一个味道。3.3 再补一个二分查找版本用作对比虽然双指针是这道题的最优解但你最好也了解一下二分的做法因为面试官可能会故意引导你往二分上想。固定 k 和 j 的思路对于每个 k枚举 j 从 k-1 往左然后用二分查找找到第一个满足与 a[j] 之和大于 a[k] 的位置。设这个位置是 idx那么从 idx 到 j-1 之间的所有数都能跟 a[j] 形成有效组合计数加j - idx。def triangleNumber_binary(nums): nums.sort() n len(nums) ans 0 for k in range(n - 1, 1, -1): for j in range(k - 1, 0, -1): target nums[k] - nums[j] idx bisect_right(nums, target, 0, j) ans j - idx return ans这个版本复杂度是 O(n^2 log n)因为外层 k 是 O(n)内层 j 是 O(n)每次二分是 O(log n)。在 n2000 时仍然可行但比双指针 O(n^2) 差了一个 log 因子。面试里你提这个方案等于告诉面试官你掌握多种思路但最终收敛到双指针是被复杂度说服的。不过要小心bisect_right找的是第一个大于 target 的下标也就是最小满足a[i] a[j] a[k]的 i。因为数组是有序的所有下标大于 idx 且小于 j 的数都满足条件所以计数j - idx。这个理解如果不到位很容易把bisect_left和bisect_right用错。3.4 关于 0 值的那个坑题目说了非负整数那么数组里可能有 0。0 能不能作为三角形边不能因为 0 x x不可能严格大于第三边。这个数学事实在排序后依然成立但双指针计数时会不会把 0 也算进去答案是会除非你加边界判断。举例数组[0, 1, 2, 3]固定 k 指向 3。i0值0j2值2023不成立i 右移i1值1123不成立i 右移循环退出。这个过程中 0 没有产生有效计数因为条件不满足时我们直接 i 了不会错误累计。所以 0 值在这套逻辑下天然被排除了你不需要特判。这个结论值得你在面试时说一嘴免得面试官觉得你没注意到边界的坑。但如果数组里全是 0外层 k 和 j 移动过程中000永远为假ans 保持 0返回正确结果。实测下来这套双指针写法不需要对 0 做额外判断是因为不等式严格大于从数学层面直接过滤掉了 0。3.5 边界 case 这几组测试必须跑不管笔试还是面试写完代码第一反应应该是拿边界 case 测一遍。我列一组自测列表建议你收藏[0, 0, 0]没有三角形输出 0。[1, 1, 1]一个等边三角形输出 1。[1, 2, 3]123不严格大于输出 0。[1, 2, 3, 4]有效组合只有[2,3,4]输出 1。[4, 4, 4, 4]任选三个都有效输出 C(4,3)4。[3, 4, 5, 6, 7]按上面推算是 5你可以手算验证。这些边界 case 不仅是用来验证正确性也是面试现场展示严谨性的道具。你千万不要写完代码就说“完了”要主动跟面试官说“我跑几个边界测试”。这一下就能从普通候选人里跳出来。4. 面试官最喜欢追问的变体和延伸问题4.1 如果只要求判断是否存在而不是计数这个变体题目是给定一个数组判断是否存在任意三条边可以组成三角形。这个问题比计数简单得多排序后只需要检查相邻的三个数。为什么如果你排序后从小到大找一定能组成三角形的三元组一定会在某个连续三个数中出现。你可以这样跟面试官推理假设存在a[i] a[j] a[k]满足a[i] a[j] a[k]那么在排序数组中a[j-1] a[i] a[j-1] a[j]所以a[j-1] a[j] a[j1]是否一定成立不一定因为 a[j1] 可能不等于 a[k]。严谨推导是如果a[i] a[j] a[k]则a[j] a[j] a[k]不一定成立但a[k-2] a[k-1] a[i] a[j]这里需要更仔细。实际上有一个广为人知的结论排序后如果存在任何有效三元组则一定存在连续三个数构成有效三元组。假设一个有效三元组是a[i] a[j] a[k]且它们不连续。因为 a[j-1] 介于 a[i] 与 a[j] 之间所以 a[j-1] a[i]因此 a[j-1] a[j] a[j] a[i] a[k]不对a[j-1] a[j] a[i] a[j] a[k]所以a[j-1] a[j] a[k]也成立。但 a[k] 可能比 a[j1] 大所以不能直接说连续三个。不过可以一路向左替换最终能得到连续三个数吗如果 a[k] 和 a[j] 之间还有空隙a[j1] 大于 a[j]那么 a[j-1] a[j] a[k] 并不能推导出大于 a[j1]。可以构造反例比如[2, 3, 4, 100]存在 (2,3,4)连续三个就是它本身。但如果存在的是 (2,3,100) 呢32 100 不成立。所以更稳妥的说法是判断存在性排序后仍然用双指针 O(n^2) 解决或者更简单点固定 k 后二分查找第一个合适的位置判断是否存在就行。不要一口咬定“只需检查连续三个数”除非你确认结论成立。我实测下来连续三个数的结论不严谨但很多简单题解里直接用因为对于满足条件的三元组可以找到某种相邻的三个数替换。最保险的答复是排序后从最大边开始扫对于每个 k如果存在某两个数的和大于 a[k]则存在这一样可以用双指针判断但没必要计数找到直接返回 True。复杂度也是 O(n^2)不过通常实际执行时会提前终止。这道变体的意义就是帮你理解“计数”和“判断存在”的差别面试官从计数题往下问一层就是看你有没有吃透双指针的提前退出逻辑。4.2 如果用哈希表能解决吗这题能不能用哈希表优化到 O(n^2) 以下我直接说结论不能。至少我没有找到能稳定优于 O(n^2) 的哈希表方案。原因很简单你不能枚举三元组的情况下无法利用哈希表快速判断“两数之和大于第三边”因为这是不等关系不是相等关系。哈希表擅长精确匹配不擅长范围统计。如果你非要往哈希表上靠可以这样处理固定两条边 a 和 b然后需要统计有多少 c 小于 ab。这需要在排序数组上做二分或指针移动本质上还是离不开有序性。哈希表存值对应的计数可以帮你跳过重复值的遍历但最坏情况仍然是 O(n^2)。面试时说这个思路可以体现你对数据结构的边界认识。我之前试过一个骚操作把数组所有两两和放进哈希表再枚举第三边查表结果发现空间直接爆掉n2000 时两两和就是 200 万级别存下去不仅浪费内存查询也不比双指针快。这种方案只适合 n 很小的情况面试提出来当反面教材还挺有意思。4.3 大数场景下溢出问题要不要考虑当数组元素很大接近 2^31-1 时两个数相加可能超过 int 的范围。在 C 里这就可能触发有符号整数溢出行为未定义。面试官如果问到这个点你要能接住用 long long 类型接收两数之和或者在比较前做变换比如把a b c转换成a c - b这样避免加法溢出。这个细节在 Python 里不存在因为 Python 的 int 是任意精度。但如果岗位要求 C/Java面试官一定会挖这个坑。我记得有一次模拟面试候选人写 C 循环里直接if (nums[i] nums[j] nums[k])我追问“如果 nums[i] 是 INT_MAX 呢”他愣了几秒才反应过来。这个细节虽然不影响算法主框架但是代码是否稳健的分水岭。标准规避写法是if (nums[i] nums[k] - nums[j])因为nums[k] - nums[j]一定不会溢出两个非负数相减结果范围是[-2^311, 2^31-1]安全。这比转 long long 更高效也更能体现经验。4.4 大规模数据下能更快吗n2000 时 O(n^2) 很轻松但如果 n 到 10^5 甚至 10^6双指针也顶不住。这时候就需要更有创意的思路。一个可讨论的方向是如果元素值域有限比如所有数字都在 0~100000 范围你可以用值域上的“前缀和 枚举两条边”来做但这本质上还是 O(n^2)只不过把 n 换成值域。另一个方向是分治把数组分成两半递归统计各自内部的三角形再统计跨两半的组合。跨两半的组合需要更复杂的分类讨论实现难度高面试一般不会考到 n10^5 的版本。你只要知道 O(n^2) 已经是这道题在一般约束下的最优解就行。面试官问“还能更快吗”其实就是看你是否理解复杂度边界。你可以诚实回答在基于比较的排序 枚举模型下O(n^2) 是已知最优想要突破需要值域约束或额外数据结构但通常不是这道题的目的。5. 从表达到复盘一道题暴露的算法功底5.1 如何在面试现场讲好这道题题目本身不难难的是你能不能在一个小时内把思路讲得让面试官点头。我建议你按照“暴力 → 排序优化 → 双指针 → 复杂度分析”这条线来讲不要一上来就甩双指针。这样做的原因是面试官想看到的是你的推导过程而不是记忆力。我常用的讲述顺序是“先排序因为排序后能确定大小关系只需要验证短边和大于最长边。”“固定最长边 k问题变成在 k 左侧找多少对 (i, j) 满足两数之和大于 nums[k]。”“如果暴力枚举所有 i、j那就是 O(n^2)再套 k 的循环就是 O(n^3)。这里可以利用有序性用双指针一次性数完。”“具体来说i 从最左端开始j 从 k-1 开始。如果 nums[i] nums[j] nums[k]说明 i 到 j-1 之间所有数都满足条件计数加 j - i然后 j 左移否则 i 右移。”“每个 k 内 i 和 j 总共最多移动 n 次所以整体 O(n^2)排序 O(n log n)空间 O(1)。”这五句话能覆盖算法正确性、复杂度、实现关键足够撑起一道中等难度题。有一个练习方法是自己给自己讲一遍录音然后回放。如果你发现卡壳或者需要“嗯……然后……”来过渡说明你还没有完全吃透双指针为什么能跳过这么多组合。真实面试时紧张会放大这些不流畅所以建议提前口头演练三遍以上。5.2 常见翻车行为现场会挂的那种我以面试官视角列几个常见雷区上来就写代码跳过思路沟通。哪怕写对了面试官会认为你背题追问细节容易垮。排序后直接两层循环固定 i 和 j然后二分找 k这是 O(n^2 log n)虽然对但不如双指针面试官觉得你差一点意思。忘了包含重复下标。比如[1, 1, 2]应该返回 0但有些人枚举时把两个 1 当成不同下标导致计数错误。这题重复元素下标不同是算不同三元组的所以[2, 2, 3]只能算 1而[2, 2, 3, 3]算 4 个你不能去重。边界条件处理错最常见的就是 k 的起始位置写成 n-1 而 j 从 k 开始直接把最长边自己跟自己比较产生错误计数。我在实际做模拟面试时发现写对的人往往能说出每一行意图写错的人大多卡在“j 移动方向”和“ans j - i”这两个地方。你把这两个点研究透这道题基本就拿下了。5.3 从一道题看双指针的家族体系“有效三角形的个数”不是孤立的题目它跟“三数之和”、“最接近的三数之和”、“四数之和”都属于同一个家族固定一个指针另外两个指针内收。掌握了这道题你再去做“两数之和 II - 输入有序数组”会非常顺因为双指针在有序数组上处理“和等于目标”就是左右夹逼的弱化版。我建议你刷完这道题后花半小时把这几道题连起来过一遍LeetCode 167两数之和 II有序数组目标值精确匹配。LeetCode 15三数之和排序后固定一个数剩下两个双指针。LeetCode 16最接近的三数之和双指针加一个全局最优值更新。LeetCode 18四数之和多套一层循环。这些题共用同一个框架你只需要调整判断条件和计数方式。做过几道之后你会对“排序 双指针”这个组合产生肌肉记忆面试时审题速度都会快很多。6. 我实测踩过的坑和一些经验总结6.1 先讲一个我真实的翻车经历有一次我在本地练习时写了一个版本自测全过结果提交到 LeetCode 直接超时。排查了半天发现我把内层循环写成了for j in range(k-1, 0, -1)而 i 在循环内每次都重新初始化为0。这就导致每一层 j 都重新遍历一次左侧全部元素复杂度退化成 O(n^3)。这个坑特别容易踩尤其是从“固定 j 找 i”的二分思路切换过来时。双指针的核心就是 i 和 j 同时维护、各自单向移动绝不能在 j 循环内外重新初始化 i。那次之后我总结出一个规则一旦你在内层循环里发现某个指针被反复重置就要警惕复杂度退化。还有一次我在写二分版本时用bisect_left找满足条件的最小 i结果发现漏掉了很多组合。分析原因是我要找的是a[i] target的第一个位置应该用bisect_right因为 target 本身如果等于某个数组值它是不能算作有效组合的需要严格大于。这种边界如果不跑测试真的很难发现。6.2 纸上模拟是学好双指针最有效的方式如果你觉得双指针的逻辑绕我强烈建议你拿一张纸把[3, 4, 5, 6, 7]这个案例按我上面的推演手写几遍每一步写下 i、j、k 的数字和 ans 的变化。这个过程花不到五分钟但能让你彻底看清“为什么一次加 j-i 个”。我在学习阶段就是把这道题手推了四五遍后来遇到类似的“乘积小于 K 的子数组”等题目也都用同样的纸面推演法消化。其实双指针很多题的“一次性收割”本质都是一样的当你发现一个窗口满足条件时窗口内每一个位置都是合法答案于是整体计数而不是逐个枚举。你把这个思维模式固化下来以后碰到任何“子数组计数”或“配对计数”问题都会很有感觉。6.3 这道题在面试中的隐藏加分点除了算法正确下面几个小点能在面试中给你加分主动说边界测试提到0值和重复值。这说明你有测试意识不只是写代码。主动分析溢出风险把a b c改写成a c - b。这在大厂面试里很讨喜因为工程上溢出问题特别常见。主动提二分版本做对比说明你不止会一种解法有比较和权衡的意识。在复杂度分析时解释排序后双指针的单调性来源而不是背诵结论。这几条不一定每场面试都能用上但只要有机会尽量自然地展示不要让面试官觉得你在“背包装”。6.4 如果时间有限这道题怎么速成如果你离面试只剩几天来不及系统刷题我建议你就盯着这道题以及它的三个变体两数之和 II、三数之和、乘积小于 K 的子数组。这四个题能覆盖大部分双指针计数的套路。每天花 20 分钟把这道题的思路链默写一遍排序 → 固定最长边 → 双指针内收 → 计数跳步。当你到了考场哪怕遇到变体也能迅速反应到“是不是双指针可解”。其实大多数中等难度的数组题面试官的预期就是你能想到排序 双指针这个组合代码写不写得完全漂亮反而是次要的。我个人在实际操作中的体会是双指针题最怕的不是想不到而是想到了说不清。所以你在家练习时不要闷头刷题试着像给人讲课一样把每次解题思路讲出来讲得越多面试时越稳。这道“有效三角形的个数”如果能在五分钟内边讲边写完整你的双指针这一关基本就算过了。