有效三角形的个数

题目 有效三角形的个数

思路分析

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

若有一条最长的边 c

一定有\(a+c>b\) 、 \(b+c>a\)

则只需要得到\(a+b>c\)

那么问题就转变成了

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

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

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

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

代码实现

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-刷题理模型 ➡️ 调整数组顺序使奇数位于偶数前面