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(nlogn)O(nlogn)。
-
双指针遍历嵌套循环耗时 O(n2)O(n2)（外层循环 O(n)O(n)，内层循环均摊 O(n)O(n)）。
-
-
空间复杂度：O(1)
-
仅使用常量额外空间（排序栈空间为 O(logn)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;
}
};
