LeetCode 611. 有效三角形的个数

约 5 分钟
文章信息 17 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 字节跳动 微软 快手 腾讯 百度 华为 拼多多 旷视 亚马逊 虾皮 哔哩哔哩
标签
数组 排序 双指针 二分查找 贪心
目录

题目描述

✅ 611. 有效三角形的个数

image-20250510225316962

题意分析

给一个非负整数数组，要统计下标三元组的个数，使得这三个位置上的数值能围成一个三角形。注意统计的是下标组合而不是数值组合：即便数组里有多个相同的数，只要下标不同就算作不同的方案，所以重复元素不能去重。

判定条件是三角形三边关系，严格来说要求任意两边之和大于第三边，共三个不等式；而且必须是严格大于，退化成一条直线的情形（两边之和恰好等于第三边）不算三角形。

约束信号是数组长度最多 1000、元素取值 0 到 1000。长度一千意味着 $O(n^2)$ 稳过、$O(n^3)$ 的三重循环在 $10^9$ 量级上会超时，这基本框定了目标复杂度。元素允许取 0 是一个明确的边界提示：含 0 的三元组永远不合法，因为 0 加任意一边都不会严格大于另一边。

其它边界：数组长度小于 3 时答案必然是 0；全为相同正数时任意三元组都合法，答案是组合数；出现大量重复值时既不能去重也不能漏计。

解法：排序后固定最长边双指针

核心思路

排序后任取三个下标 i < j < k，都有 nums[i] <= nums[j] <= nums[k]。三角形的三条不等式中，前两条会自动成立，只需检查两条较短边之和是否严格大于最长边：

nums[i] + nums[j] > nums[k]

固定最长边 k，问题变成在有序区间 [0, k-1] 中统计满足条件的数对。令 left=0、right=k-1：

  • 若 nums[left] + nums[right] > nums[k]，那么第一条边取 left..right-1 都成立，因为这些值只会更大。因此可一次计入 right-left 个组合，再令 right--。
  • 否则，即使当前最大的第二条短边 nums[right] 也无法与 nums[left] 成三角形，换成更小的数更不可能成立，因此令 left++。

循环不变量是：位于当前双指针区间之外、以 k 为最长边的组合都已经被正确统计或排除。每次移动都能整段结算一类组合，所以单个 k 只需线性时间。每个三元组也只会在其最大下标作为 k 时被统计一次，因而不重不漏。

解题步骤

  • 将数组升序排序，使最大边固定在三个下标的最右侧。
  • 从 k=n-1 到 2 枚举最长边，初始化 left=0、right=k-1。
  • 当 left < right 时比较 nums[left] + nums[right] 与 nums[k]。
  • 若严格大于，累加 right-left 并左移 right；否则右移 left。
  • 返回累计数量。

例如 [2,2,3,4]：固定 4 时，2+3>4，一次计入两种下标组合；固定 3 时，2+2>3，再计入一种，答案为 3。注意 2+2=4 是退化线段，不能计数。

代码实现

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(n)$ 次。
  • 空间复杂度：$O(\log n)$，来自排序的调用栈；双指针本身只使用 $O(1)$ 额外空间。

关键点总结

  • 排序后只需验证“两个较小值之和严格大于最大值”。
  • 命中时能批量累加 right-left，是复杂度从三次方降到平方的关键。
  • 指针移动由单调性决定：命中后缩小较大短边，未命中时增大较小短边。
  • 题目统计下标三元组，重复数值不能去重；排序会修改输入数组，如业务场景要求保留原序应先复制。

易错点总结

  • 判定必须使用 > 而不是 >=；例如 [2,2,4] 不能组成三角形。
  • 命中时应累加 right-left，只加 1 会漏掉这一整段合法的第一条边。
  • 未排序就使用双指针，最大边位置和单调性都不成立。
  • 命中后只移动 right；同时移动 left 会漏掉它与更小 right 的组合，例如 [1,1,1,1]。
  • 循环条件必须是 left < right，否则会重复使用同一个下标。

相似题目

题目 难度 考察点
15. 三数之和 中等 目标是和恰好为 0 且要输出具体解，必须显式跳过重复值去重
16. 最接近的三数之和 中等 求与目标最接近的和，维护最优差值而非计数
18. 四数之和 中等 多固定一层循环变成两重枚举加双指针，还要防止求和溢出
167. 两数之和 II - 输入有序数组 中等 输入已有序，直接相向双指针求唯一一对下标
259. 较小的三数之和 中等 不等号方向相反，命中时批量累加的区间落在 mid 一侧
1099. 小于 K 的两数之和 简单 两元组版本，求满足上界的最大和而不是方案数
LCR 006. 两数之和 II - 输入有序数组 简单 167 的同题异号版本，注意返回的是从 0 开始的下标
LCR 007. 三数之和 中等 15 的同题异号版本，同样要处理三处重复值跳过
剑指 Offer 57. 和为s的两个数字 简单 有序数组求和为定值的任意一对，命中即可返回无需继续扫描
面试题 16.24. 数对和 中等 每个元素最多用一次，要不断取走配对成功的两端而非只做统计