LeetCode 611. 有效三角形的个数
题目描述
题意分析
给定非负整数数组，从三个不同下标各取一个数作为边长，统计能组成非退化三角形的组合数量。同一组三个下标只计一次，数值相同但下标不同的元素仍分别参与组合。
三角形要求任意两边之和严格大于第三边。把三条边排序为
a <= b <= c后，只需判断a + b > c：它同时保证最小边为正，另外两条不等式便自然成立。长度为零的边或两短边之和恰好等于长边，都不能计入。
解法：排序后固定最长边双指针
核心思路
[!blue]
先将数组升序排序。固定最长边下标
k后，另外两个下标只能来自[0, k)，问题转为统计其中有多少对数的和严格大于nums[k]。每个三元组都恰好属于其最右下标对应的一轮，不会在不同k之间重复计数。用
left = 0、right = k - 1表示尚待统计的候选范围。如果nums[left] + nums[right] > nums[k]，由于数组升序，第一条边取任何left <= i < right都满足条件。因此固定当前right的这些组合可以一次计入right - left个，再将right左移，处理更小的第二条边。如果两者之和不够大，当前
left配上范围内最大的right都失败，配上任何更靠左、更小的第二条边也一定失败。因此可以排除当前left，令它右移，而不会漏掉答案。这两个分支每次都完整处理一个边界：成功时处理当前
right对应的全部可行第一条边，失败时排除当前left对应的全部剩余组合。一直收缩到left == right，当前最长边的统计就完成了。不同下标的重复值需要照常保留，不使用三数之和中按数值去重的逻辑。
解题步骤
- 将数组升序排序，初始化答案为零。
- 从
k = n - 1到2枚举最长边，令left = 0、right = k - 1。- 当
left < right时，比较两短边之和与nums[k]。- 若严格大于，累加
right - left并将right减一；否则将left加一。- 汇总各个最长边对应的数量，返回答案。元素不足三个时，外层循环自然不执行。
代码实现
class Solution {
public int triangleNumber(int[] nums) {
java.util.Arrays.sort(nums);
int ans = 0;
for (int k = nums.length - 1; k >= 2; k--) {
int left = 0;
int right = k - 1;
while (left < right) {
if (nums[left] + nums[right] > nums[k]) {
// 当前最小候选已能成三角形，其右侧到右端之前的值都同样可行。
ans += right - left;
right--;
} else {
left++;
}
}
}
return ans;
}
}
import "sort"
func triangleNumber(nums []int) int {
sort.Ints(nums)
ans := 0
for k := len(nums) - 1; k >= 2; k-- {
left, right := 0, k-1
for left < right {
if nums[left]+nums[right] > nums[k] {
// 当前最小候选已能成三角形，其右侧到右端之前的值都同样可行。
ans += right - left
right--
} else {
left++
}
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n^2)$。排序需要 $O(n\log n)$；固定每个
k后，两指针合计移动 $O(k)$ 次，全部扫描合计为平方量级。- 空间复杂度：双指针本身为 $O(1)$，整体取决于排序实现。Go 排序只递归较短分区，栈空间为 $O(\log n)$；Java 的排序合并路径可能分配 $O(n)$ 临时数组，保守按 $O(n)$ 计。实现依据见 Go 排序源码 和 OpenJDK 排序源码。
关键点总结
[!green]
- 固定最右下标，就固定了最长边，并让每个下标三元组只归入一轮。
- 命中条件后批量累加
right - left，是把三重枚举降为双重扫描的关键。- 排序后的单调性分别证明了成功时左移
right、失败时右移left的安全性。- 统计的是下标组合，重复数值不能去重；当前实现会直接排序并修改输入数组。
易错点总结
[!yellow]
- 条件必须是严格大于，使用
>=会把退化成线段的组合也算作三角形。- 命中时只加一，会漏掉当前
right与整个可行前缀的组合，应加right - left。- 命中后同时移动
left，会漏掉它与下一个较小right的组合；当前分支只处理完了right。- 未排序就使用这些指针移动规则，无法保证被跳过的组合都已统计或确定无效。
- 必须保持
left < right < k，否则可能把同一个数组位置当作两条边使用。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 976. 三角形的最大周长 | 简单 | 同样排序后使用两短边和大于长边，本题累计全部组合，原题只取最大周长。 |
| 259. 较小的三数之和 | 中等 | 同样固定一项后用双指针批量计数，本题条件是两边和大于第三边，原题三数和小于目标。 |
| 15. 三数之和 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题把三角不等式转为两数和比较，该题固定一个数寻找零和三元组。 |
| 16. 最接近的三数之和 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题把三角不等式转为两数和比较，该题根据与目标的距离更新最接近的和。 |
| 18. 四数之和 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题把三角不等式转为两数和比较，该题多固定一个数寻找四元组。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！