题目描述
思路解析动画文字版
记住「排序→固定最大边→对撞双指针:和够大就一次加 r−l 个、r 左移;不够就 l 右移」,下面每帧都在套它。
第一步排序。原数组是 [8, 2, 6, 4, 3, 5],排好序变成 [2, 3, 4, 5, 6, 8]。排序是后面双指针的前提:有了顺序,固定最右边那个就是当前最大边,左边的数也单调,指针才能稳稳对撞。
固定最大的那条边 nums[5]=8（黄色）。只要在它左边能找到两条边、和严格大于 8，就凑成一个三角形。左指针 l 从最左、右指针 r 紧挨最大边,往中间夹。
当前两条边是 nums[0]=2 和 nums[4]=6，它们的和是 8。下一步看这个和是不是严格大于最大边 8。
8 没有大于 8，凑不成三角形。问题出在最小的那条边 nums[0]=2 太短,把它换掉:l 右移一格到 1,去试更大的最小边。
当前两条边是 nums[1]=3 和 nums[4]=6，它们的和是 9。下一步看这个和是不是严格大于最大边 8。
9 严格大于 8，成立!这里有个关键省时:既然最小的 nums[1]=3 配 nums[4]=6 都够大,那把 l 换成 1 到 3 之间任何一个更大的数,配 nums[4] 和最大边一样成立,所以一次就能记下 r−l=3 个三角形。记完让 r 左移一格,去试更小的右边。
当前两条边是 nums[1]=3 和 nums[3]=5，它们的和是 8。下一步看这个和是不是严格大于最大边 8。
8 没有大于 8，凑不成三角形。问题出在最小的那条边 nums[1]=3 太短,把它换掉:l 右移一格到 2,去试更大的最小边。
当前两条边是 nums[2]=4 和 nums[3]=5，它们的和是 9。下一步看这个和是不是严格大于最大边 8。
9 严格大于 8，成立!这里有个关键省时:既然最小的 nums[2]=4 配 nums[3]=5 都够大,那把 l 换成 2 到 2 之间任何一个更大的数,配 nums[3] 和最大边一样成立,所以一次就能记下 r−l=1 个三角形。记完让 r 左移一格,去试更小的右边。
固定最大的那条边 nums[4]=6（黄色）。只要在它左边能找到两条边、和严格大于 6，就凑成一个三角形。左指针 l 从最左、右指针 r 紧挨最大边,往中间夹。
当前两条边是 nums[0]=2 和 nums[3]=5，它们的和是 7。下一步看这个和是不是严格大于最大边 6。
7 严格大于 6，成立!这里有个关键省时:既然最小的 nums[0]=2 配 nums[3]=5 都够大,那把 l 换成 0 到 2 之间任何一个更大的数,配 nums[3] 和最大边一样成立,所以一次就能记下 r−l=3 个三角形。记完让 r 左移一格,去试更小的右边。
当前两条边是 nums[0]=2 和 nums[2]=4，它们的和是 6。下一步看这个和是不是严格大于最大边 6。
6 没有大于 6，凑不成三角形。问题出在最小的那条边 nums[0]=2 太短,把它换掉:l 右移一格到 1,去试更大的最小边。
当前两条边是 nums[1]=3 和 nums[2]=4，它们的和是 7。下一步看这个和是不是严格大于最大边 6。
7 严格大于 6，成立!这里有个关键省时:既然最小的 nums[1]=3 配 nums[2]=4 都够大,那把 l 换成 1 到 1 之间任何一个更大的数,配 nums[2] 和最大边一样成立,所以一次就能记下 r−l=1 个三角形。记完让 r 左移一格,去试更小的右边。
固定最大的那条边 nums[3]=5（黄色）。只要在它左边能找到两条边、和严格大于 5，就凑成一个三角形。左指针 l 从最左、右指针 r 紧挨最大边,往中间夹。
当前两条边是 nums[0]=2 和 nums[2]=4，它们的和是 6。下一步看这个和是不是严格大于最大边 5。
6 严格大于 5，成立!这里有个关键省时:既然最小的 nums[0]=2 配 nums[2]=4 都够大,那把 l 换成 0 到 1 之间任何一个更大的数,配 nums[2] 和最大边一样成立,所以一次就能记下 r−l=2 个三角形。记完让 r 左移一格,去试更小的右边。
当前两条边是 nums[0]=2 和 nums[1]=3，它们的和是 5。下一步看这个和是不是严格大于最大边 5。
5 没有大于 5，凑不成三角形。问题出在最小的那条边 nums[0]=2 太短,把它换掉:l 右移一格到 1,去试更大的最小边。
固定最大的那条边 nums[2]=4（黄色）。只要在它左边能找到两条边、和严格大于 4，就凑成一个三角形。左指针 l 从最左、右指针 r 紧挨最大边,往中间夹。
当前两条边是 nums[0]=2 和 nums[1]=3，它们的和是 5。下一步看这个和是不是严格大于最大边 4。
5 严格大于 4，成立!这里有个关键省时:既然最小的 nums[0]=2 配 nums[1]=3 都够大,那把 l 换成 0 到 0 之间任何一个更大的数,配 nums[1] 和最大边一样成立,所以一次就能记下 r−l=1 个三角形。记完让 r 左移一格,去试更小的右边。
每个能当三元组最大边的位置(k 从 2 到 5)都固定过一遍、各跑一趟双指针,累计 11 个有效三角形,就是答案。回头看:排序 + 固定最大边 + 对撞双指针,把暴力枚举三元组的 O(n³) 压到了 O(n²)。
边界:不足三个数、含 0 边、最小两边和等于或小于最大边,都不算有效三角。
认出「排序 + 双指针」母题,固定最大边是这道题的关键选择。
参考代码
from typing import Listclass Solution: def triangleNumber(self, nums: List[int]) -> int: nums.sort() ans = 0 for k in range(len(nums) - 1, 1, -1): l, r = 0, k - 1 while l < r: if nums[l] + nums[r] > nums[k]: ans += r - l r -= 1 else: l += 1 return ans复杂度
- 时间：O(n²)，排序 O(n log n);固定每条最大边各跑一趟双指针,合起来 O(n²)
- 空间：O(log n)~O(n)，只用几个指针,额外开销主要在排序:C++/Java 通常 O(log n),Python 的 Timsort 最坏 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么固定最大边、而不是固定最小边?
追问和「三数之和」类题有什么共性?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
匹配子序列的单词数
LeetCode 792 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题