当前位置：首页 > article >正文

1.5 双指针专题：有效三⻆形的个数（medium）

article 2025/3/12 9:26:04

1.题目链接

611. 有效三角形的个数 - 力扣（LeetCode）https://leetcode.cn/problems/valid-triangle-number/submissions/609232447/

2.题目描述

给定⼀个包含⾮负整数的数组 nums ，返回其中可以组成三⻆形三条边的三元组个数。

⽰例 1:

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

解释:有效的组合是:

2,3,4 (使⽤第⼀个 2)
2,3,4 (使⽤第⼆个 2)
2,2,3

⽰例 2:

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

解释：

4,2,3
4,2,4
4,3,4
2,3,4

3.算法思路

该算法用于计算数组中能构成三角形的三元组数量，通过排序与双指针法高效遍历可能组合。核心思路是固定最长边，寻找满足两边之和大于第三边的较小边组合。具体步骤如下：

1. 排序预处理

将数组 nums 升序排序，使得后续能通过双指针快速定位有效组合。
目的：三角形的边长需满足 a+b>ca+b>c（假设 a≤b≤ca≤b≤c），排序后只需固定 cc 并寻找 aa 和 bb 的组合。

2. 外层循环固定最长边

从最大值开始遍历，设当前最长边为 nums[i]（i 从 n-1 递减到 2）。
原因：固定 c=nums[i]c=nums[i] 后，只需在 [0, i-1] 范围内寻找满足 a+b>ca+b>c 的 aa 和 bb。

3. 双指针寻找有效组合

初始化：左指针 left = 0，右指针 right = i - 1。
条件判断：
- 若 nums[left] + nums[right] > nums[i]，则 left 到 right-1 的所有元素与 right 均满足条件，累加组合数 ret += right - left，并左移 right 以尝试更小的右边界。
- 否则，右移 left 以增大最小边，尝试满足条件。
终止：当 left >= right 时结束内层循环。

正确性证明

组合计数逻辑：
当 nums[left] + nums[right] > nums[i] 时，由于数组有序，nums[left ... right-1] 均满足与 nums[right] 的和大于 nums[i]，因此可直接累加 right - left 个组合。
指针移动策略：
移动较小边（left）或较大边（right）确保不漏解。若和不足，必须增大较小边；若和足够，则记录所有可能组合后缩小较大边。

示例分析

输入：nums = [2, 3, 4, 5]
- 排序后为 [2, 3, 4, 5]。
- 外层循环 i=3（最长边5）：
  - left=0, right=2 → 2+4=6>5 → 累加 2-0=2 个组合（(2,4,5)、(3,4,5)）。
  - right=1 → 2+3=5≯5 → left++ → 循环结束。
- 外层循环 i=2（最长边4）：
  - left=0, right=1 → 2+3=5>4 → 累加 1-0=1 个组合（(2,3,4)）。
- 总计：3 个有效三元组。

复杂度分析

时间复杂度：O(n²)
- 排序耗时 O(nlog⁡n)O(nlogn)。
- 双指针遍历嵌套循环耗时 O(n2)O(n2)（外层循环 O(n)O(n)，内层循环均摊 O(n)O(n)）。
空间复杂度：O(1)
- 仅使用常量额外空间（排序栈空间为 O(log⁡n)O(logn)，通常不计入）。

关键点总结

排序的必要性：通过有序性快速缩小搜索范围，避免暴力枚举。
双指针的优化：将组合数计算从 O(n3)O(n3) 优化至 O(n2)O(n2)。
贪心策略：固定最长边后，动态调整双指针确保不漏解，高效统计有效组合。

4.代码实现

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        int ret = 0, n = nums.size();
        for(int i = n - 1; i >= 2 ;i--)
        {
            int left = 0, right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    ret = right - left + ret;
                    right--;
                }
                else left++;
            }
        }
        return ret;
    }
};