C++ 合法的三角形个数

题目：给一个长度为N的非负整数数组nums，请你计算一下，有多少个三元组代表的边长可以组成三角形数据范围 :1≤N≤1000，*0≤nums[i]≤1000*该题的解法如下：首先，对各边长进行排序，方便获取三边中最长的边。然后，进入循环，循环体如下：由小到大找最长边（循环）从最长边开始由大到小找次长边（循环）从次长边开始由大到小找最短边。(循环计数法，或者用二分查找法找上界，然后用计算中间个数）

int validTriangleNumber(vector<int>& nums)
    {
        int length = nums.size();
        if (length < 3) return 0;
        sort(nums.begin(), nums.end());
        int res = 0;
        for (int right = 2; right < length; ++right)
        {
            for (int mid = right - 1; mid > 0; --mid)
            {
                int temp = nums[right] - nums[mid];
                if (temp > nums[mid]) break;
                auto bg = nums.begin();
                auto upperBound = upper_bound(bg, bg + mid, temp);
                res += mid - (upperBound - bg);
            }
        }
        return res;
    }

//二分查找上界法
        int validTriangleNumber(vector<int>& nums)
    {
        int length = nums.size();
        if (length < 3) return 0;
        sort(nums.begin(), nums.end());//排序
                int res = 0;
        for (int right = 2; right < length; ++right)//right最长边序号
        {
            for (int mid = right - 1; mid > 0; --mid)//mid次长边序号
            {
                int temp = nums[right] - nums[mid];//找出最短边的最短长度temp
                if (temp > nums[mid]) break;//如果最短边长度的最短长度已经比次长长，打断循环
                auto bg = nums.begin();
                auto upperBound = upper_bound(bg, bg + mid, temp);//利用二分法找出最短边长度上界
                res += mid - (upperBound - bg);//计算中间边的个数
            }
        }
        return res;
    }

原文链接: https://www.cnblogs.com/mshentaiBlog/p/15808791.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍