---
title: "有效三角形的个数"
created: 2025-11-28
tags:
  - 算法
---

# 有效三角形的个数

## 题目 [有效三角形的个数](https://leetcode.cn/problems/valid-triangle-number/description/)

![[image-f71906ff.png]]

## 思路分析

在三角形中，任意一条边的长度都小于另外两条边的长度之和

若有一条最长的边 c

一定有$a+c>b$     、
$b+c>a$

则只需要得到$a+b>c$

那么问题就转变成了

一个指针i一个指针j从两头对撞 将a[i]+a[j]与某个数x对比的题

这个数x从哪来 其实也是这个数组里面

那么就是 遍历整个数组 对每个数在该数组里面找一组满足的数

当然这一切的大前提是要排好序（构造出单调性）

![[image-7e35b25f.png]]

## 代码实现

```java
class Solution {

public:

    int triangleNumber(vector<int>& nums) {

        sort(nums.begin(), nums.end());

        int n = nums.size(), ans = 0;

        for (int k = n-1; k > 1; k--) {

            for(int i = k-1,j=0; i>j; i--){

                while (j<i && nums[i] + nums[j] <= nums[k]) {

                    j++;

                }

                ans+=max(i-j,0);

            }

        }

        return ans;

    }

};
```

## 同类题型

## 视频讲解

---
⬅️ [[有序数组的平方|有序数组的平方]] 🏠 [[00-刷题理模型]] ➡️ [[调整数组顺序使奇数位于偶数前面|调整数组顺序使奇数位于偶数前面]]