有效三角形的个数-LeetCode

611. 有效三角形的个数

🎯 问题描述（来源于LeetCode）

描述：
给定一个包含非负整数的数组 nums，返回其中可以组成三角形三条边的三元组个数。
三角形的条件是：任意两边之和大于第三边，等价于较短两边之和大于最长边。

说明：

• 三元组 (i, j, k) 满足 i < j < k，且 nums[i] + nums[j] > nums[k]。
• 数组长度 1 <= n <= 1000。

示例：

• 示例 1：

输入: nums = [2,2,3,4]
输出: 3
解释: 有效组合: (2,2,3), (2,3,4), (2,3,4) 共 3 个。

• 示例 2：

输入: nums = [4,2,3,4]
输出: 4

💻 解题思路

思路：排序 + 双指针（固定最短边，滑动中边）

算法步骤

1. 将数组 nums 升序排序。
2. 外层循环 slow 从 0 到 n-3，固定最短边 num = nums[slow]。
   如果 num == 0，由于三角形边长必须为正数，直接跳过。
3. 初始化 mid = slow + 1，指向可能的次短边（中边）的起始位置。
4. 内层循环 fast 从 slow+2 到 n-1，枚举最长边 c = nums[fast]：
   • 当 nums[fast] - nums[mid] >= num 时，说明 num + nums[mid] <= nums[fast]，不满足三角形条件（两边之和不大于第三边）。此时将 mid 右移，直到满足 num + nums[mid] > nums[fast]。
   • 此时，所有下标从 mid 到 fast-1 的元素都可以作为中边 b，与当前的 num 和 nums[fast] 组成三角形。
     可行数量为 fast - mid，累加到答案 ans。
5. 返回 ans。

代码实现（您的代码）

from typing import List

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        ans = 0
        for slow in range(n - 2):
            num = nums[slow]
            if num == 0:  
                continue
            mid = slow + 1
            for fast in range(slow + 2, n):
                while nums[fast] - nums[mid] >= num:
                    mid += 1
                ans += fast - mid
        return ans

📊 性能分析

• 时间复杂度：$O(n^2)$。外层循环 $O(n)$，内层循环中 fast 和 mid 均单调递增，每个指针最多移动 $O(n)$ 次，总体 $O(n^2)$。
• 空间复杂度：$O(1)$（忽略排序占用的栈空间）。

思考

您的命名 slow, mid, fast 非常形象：

• slow 是最短边，固定不变；
• fast 是最长边，不断右移；
• mid 是中边，随着 fast 增大和 num 固定，为了满足 num + nums[mid] > nums[fast]，mid 只能向右移动，绝不回头。

利用排序后的单调性，mid 的单向移动保证了内层循环的摊还复杂度为 $O(n)$，整体达到 $O(n^2)$，这是本题的标准最优解法。跳过 0 的处理也避免了对无效边长进行多余计算，代码逻辑清晰且高效。