当前位置:网站首页>611. 有效三角形的个数

611. 有效三角形的个数

2022-07-05 07:18:00 BugMaker-shen

在这里插入图片描述
611. 有效三角形的个数

在这里插入图片描述

此时 n u m s [ l ] + n u m s [ m i d ] > n u m s [ r ] nums[l] + nums[mid] > nums[r] nums[l]+nums[mid]>nums[r] l l l [ l , m i d − 1 ] [l,mid-1] [l,mid1]内任何一个数都满足条件,故有 a n s + = ( m i d − l ) ans += (mid - l) ans+=(midl)

我们现在的三元组(2,6,7)满足条件了,由于不等式右侧nums[r]固定,我们需要做的是调整不等式左侧的大小,尽可能让不等式满足

由于我们让 l l l [ l , m i d − 1 ] [l,mid-1] [l,mid1]内任何一个数就是尝试了让不等式左侧变得更大(依然满足条件),我们现在应该让不等式左侧变得更小,继续查看是否满足三角形条件,即向左移动mid,继续查找三元组

在这里插入图片描述
不满足条件时,两个小数字的和太小了,要让不等式左侧变大,只有一个选择:向右移动 l l l取更大的数

class Solution {
    
public:
    int triangleNumber(vector<int>& nums) {
    
        sort(nums.begin(), nums.end(), less<int>());
        int n = nums.size();
        int ans = 0;
        // 每轮循环固定最大的数字不动
        for (int r = n - 1; r >= 2; r--){
    
            int l = 0;
            int mid = r - 1;
            while(l < mid){
    
                if(nums[l] + nums[mid] > nums[r]){
    
                    ans += (mid - l);
                    // mid是从r-1开始的,mid初始值较大,现在已经满足三角形条件,需要在较小数字中找满足三角形条件的数字
                    mid--;
                }else{
    
                    // 两个小数字的和太小了
                    l++;
                }
            }
        }
        return ans;
    }
};

那我们可以固定最小的值,用mid和r寻找三元组吗?
在这里插入图片描述

这种情况下,不满足三角形条件,两个小数字之和太小了,我们可以向右调整 m i d mid mid n u m s [ l ] + n u m s [ m i d ] nums[l]+nums[mid] nums[l]+nums[mid]的值更大,或向左调整 r r r,让 n u m s [ r ] nums[r] nums[r]的值更小,以满足三角形不等式。这操作起来就比较困难了:

我们向右调整mid,mid指向3,我们会漏掉(2,2,3)这个组合;向左调整r,r指向3,我们会漏掉(2,3,4)这个组合

所以我们应该把用于搜索三元组的两个指针放在不等式的同一侧,使得不满足三角形不等式时只有一个选择

原网站

版权声明
本文为[BugMaker-shen]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_42500831/article/details/125586522