企业官网建设流程全解析

有效三角形的个数，一道必刷的经典题

“面试必看：有效三角形的个数”，这标题我信一半。真正面试过的人心里都有数，面热点题这事儿，既考刷题量，也考讲题的逻辑。但“有效三角形的个数”这一道，属于那种看似数学、实则是纯双指针套路的题，它不考你三角不等式推得多深，考的是你能不能看穿排序后指数规模降维的那一下。我见过太多人卡在“为什么 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 甚至 2000，O(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而不是从i+1开始，是我当初学这道题时最容易想不通的点。要解释清楚：因为两个数从两端逼近中间时，能利用“右端最大”这个信息，一旦右端加上当前左端已经大于目标，那么当前左端到右端之间的所有数，跟右端配对一定都满足条件。如果你从 i+1 开始，从左往右扫，那么你需要一个个试探 j 往右延伸到哪里才停止，无法实现一次跳多个计数。

2.2 双指针单调性到底体现在哪里

双指针解法的正确性根源，在于两个指针移动过程中“单调性”的保持。你要意识到，当你固定a[k]后，a[i]在增大，a[j]在减小。每轮循环，如果a[i] + a[j] > a[k]，那么所有a[i+1]到a[j-1]与a[j]配对都必然满足条件吗？不一定，因为 a[i+1] 比 a[i] 更大，所以a[i+1] + a[j] > a[k]一定成立。这句话是对的，因为加数变大了，和只会变大。

反过来，如果a[i] + a[j] <= a[k]，说明当前的 a[i] 太小了，就算配上目前最大的 a[j] 也不够。那更小的左端值就更不可能够。所以此时唯一的选择是让 i 向右移动，换一个更大的 a[i]。

这个“其中一个指针移动后，另一个指针的可行区间只会单向变化”的特性，就是双指针能在线性时间内完成计数的一整套逻辑。它比二分还难想一点，因为你要理解“为什么不需要回溯”。左指针做过的事情，右指针不会回到过去重新检查，因为问题域的单调性保证了不会漏解。

拿真实数据举例：数组[1, 2, 3, 4, 5]，固定 k 指向 5，i 指向 1，j 指向 4，1 + 4 > 5不成立，所以 i 移到 2；2 + 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)，这是标准排序的时间。

接下来外层循环固定 k，k 从 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)，那 k=1 时 i=0、j=0，循环根本不入口，白跑一次。

第二，内层双指针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？此时 i=3、j=3，循环退出。总计数是 4？等等，好像还少了一个 (4,5)。让我重新模拟一遍。

数组[3, 4, 5, 6, 7]，k 指向 7。i=0 (值3)，j=3 (值6)。3+6>7成立，ans+=3（代表组合：(3,6)、(4,6)、(5,6)），j 左移到值 5（下标2）。此时 i=0 (3)，j=2 (5)。3+5>7成立，ans+=2（代表组合：(3,5)、(4,5)），j 左移到值 4（下标1）。此时 i=0 (3)，j=1 (4)。3+4>7不成立，i 右移到下标1。i=1 (4)，j=1 (4)，i >= j，退出。总计 ans=5。完美。

这里我一开始误算了 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)。在 n=2000 时仍然可行，但比双指针 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。i=0（值0），j=2（值2），0+2>3不成立，i 右移；i=1（值1），1+2>3不成立，i 右移；循环退出。这个过程中 0 没有产生有效计数，因为条件不满足时我们直接 i++ 了，不会错误累计。所以 0 值在这套逻辑下天然被排除了，你不需要特判。这个结论值得你在面试时说一嘴，免得面试官觉得你没注意到边界的坑。

但如果数组里全是 0，外层 k 和 j 移动过程中，0+0>0永远为假，ans 保持 0，返回正确结果。实测下来，这套双指针写法不需要对 0 做额外判断，是因为不等式严格大于从数学层面直接过滤掉了 0。

3.5 边界 case 这几组测试必须跑

不管笔试还是面试，写完代码第一反应应该是拿边界 case 测一遍。我列一组自测列表，建议你收藏：

• [0, 0, 0]：没有三角形，输出 0。
• [1, 1, 1]：一个等边三角形，输出 1。
• [1, 2, 3]：1+2=3，不严格大于，输出 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[j+1]是否一定成立？不一定，因为 a[j+1] 可能不等于 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[j+1] 大，所以不能直接说连续三个。不过可以一路向左替换，最终能得到连续三个数吗？如果 a[k] 和 a[j] 之间还有空隙，a[j+1] 大于 a[j]，那么 a[j-1] + a[j] > a[k] 并不能推导出大于 a[j+1]。可以构造反例，比如[2, 3, 4, 100]，存在 (2,3,4)，连续三个就是它本身。但如果存在的是 (2,3,100) 呢，3+2 > 100 不成立。

所以更稳妥的说法是：判断存在性排序后仍然用双指针 O(n^2) 解决，或者更简单点，固定 k 后二分查找第一个合适的位置，判断是否存在就行。不要一口咬定“只需检查连续三个数”，除非你确认结论成立。我实测下来，连续三个数的结论不严谨，但很多简单题解里直接用，因为对于满足条件的三元组，可以找到某种相邻的三个数替换。最保险的答复是：排序后从最大边开始扫，对于每个 k，如果存在某两个数的和大于 a[k]，则存在；这一样可以用双指针判断，但没必要计数，找到直接返回 True。复杂度也是 O(n^2)，不过通常实际执行时会提前终止。

这道变体的意义就是帮你理解“计数”和“判断存在”的差别，面试官从计数题往下问一层，就是看你有没有吃透双指针的提前退出逻辑。

4.2 如果用哈希表，能解决吗

这题能不能用哈希表优化到 O(n^2) 以下？我直接说结论：不能。至少我没有找到能稳定优于 O(n^2) 的哈希表方案。原因很简单，你不能枚举三元组的情况下，无法利用哈希表快速判断“两数之和大于第三边”，因为这是不等关系，不是相等关系。哈希表擅长精确匹配，不擅长范围统计。

如果你非要往哈希表上靠，可以这样处理：固定两条边 a 和 b，然后需要统计有多少 c 小于 a+b。这需要在排序数组上做二分或指针移动，本质上还是离不开有序性。哈希表存值对应的计数，可以帮你跳过重复值的遍历，但最坏情况仍然是 O(n^2)。面试时说这个思路，可以体现你对数据结构的边界认识。

我之前试过一个骚操作：把数组所有两两和放进哈希表，再枚举第三边查表，结果发现空间直接爆掉，n=2000 时两两和就是 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^31+1, 2^31-1]，安全。这比转 long long 更高效，也更能体现经验。

4.4 大规模数据下，能更快吗？

n=2000 时 O(n^2) 很轻松，但如果 n 到 10^5 甚至 10^6，双指针也顶不住。这时候就需要更有创意的思路。一个可讨论的方向是，如果元素值域有限，比如所有数字都在 0~100000 范围，你可以用值域上的“前缀和 + 枚举两条边”来做，但这本质上还是 O(n^2)，只不过把 n 换成值域。

另一个方向是分治：把数组分成两半，递归统计各自内部的三角形，再统计跨两半的组合。跨两半的组合需要更复杂的分类讨论，实现难度高，面试一般不会考到 n=10^5 的版本。你只要知道 O(n^2) 已经是这道题在一般约束下的最优解就行。

面试官问“还能更快吗”，其实就是看你是否理解复杂度边界。你可以诚实回答：在基于比较的排序 + 枚举模型下，O(n^2) 是已知最优，想要突破需要值域约束或额外数据结构，但通常不是这道题的目的。

5. 从表达到复盘：一道题暴露的算法功底

5.1 如何在面试现场讲好这道题

题目本身不难，难的是你能不能在一个小时内把思路讲得让面试官点头。我建议你按照“暴力 → 排序优化 → 双指针 → 复杂度分析”这条线来讲，不要一上来就甩双指针。这样做的原因是，面试官想看到的是你的推导过程，而不是记忆力。

我常用的讲述顺序是：

1. “先排序，因为排序后能确定大小关系，只需要验证短边和大于最长边。”
2. “固定最长边 k，问题变成：在 k 左侧找多少对 (i, j) 满足两数之和大于 nums[k]。”
3. “如果暴力枚举所有 i、j，那就是 O(n^2)，再套 k 的循环就是 O(n^3)。这里可以利用有序性，用双指针一次性数完。”
4. “具体来说，i 从最左端开始，j 从 k-1 开始。如果 nums[i] + nums[j] > nums[k]，说明 i 到 j-1 之间所有数都满足条件，计数加 j - i，然后 j 左移；否则 i 右移。”
5. “每个 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 分钟把这道题的思路链默写一遍：排序 → 固定最长边 → 双指针内收 → 计数跳步。

当你到了考场，哪怕遇到变体，也能迅速反应到“是不是双指针可解”。其实大多数中等难度的数组题，面试官的预期就是你能想到排序 + 双指针这个组合，代码写不写得完全漂亮反而是次要的。

我个人在实际操作中的体会是，双指针题最怕的不是想不到，而是想到了说不清。所以你在家练习时不要闷头刷题，试着像给人讲课一样把每次解题思路讲出来，讲得越多，面试时越稳。这道“有效三角形的个数”如果能在五分钟内边讲边写完整，你的双指针这一关基本就算过了。