611. 有效三角形的个数 - 力扣

1. 题目

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

2. 示例

3. 分析 

利用已升序了的数组通过 a + b > c 这条公式找出符合要求的三元组，利用这个公式的前提是三条边为从小到大，再利用单调性快速统计出符合要求的三元组个数。

解题方法：

1. 先固定到最大的数(c)，即nums[nums.size()-1]。
2. 再最大数的左区间内，定位一左(a)一右(b)指针分别指向区间左右。

现在就可以开始寻找符合要求的三条边了。
两边之和有两种情况：

• a + b > c
  这是符合要求的情况。我们知道数组是升序的，因为此时 left(a) + right(b) 已经是大于 c 了，那么[left+1, right-1] (a)这个区间内的数 + right(b) 也是肯定大于 c 了，因为数组是升序的(单调性)。所以此时符合要求的三元组个数就为(right-left)，这个组合下的right(b)可以舍弃掉了，再--看下一个b的情况即可。
• a + b <= c
  这是不符合要求的情况，为无效三角形。因为此时 left(a) + right(b) 已经是小于或等于 c 了，那么[left+1, right-1] (a)这个区间内的数 + right(b) 也是肯定小于或等于 c 了，因为数组是升序的(单调性)。这个组合下的left(a)可以舍弃掉了，再++看下一个a的情况即可。

当区间内的所以情况判断完毕，即最大数的所有组合已统计完毕，再重新固定新的最大数，即上一个最大数的前一位数，再去统计符合要求的三元组个数。

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        // 1. 升序
        sort(nums.begin(), nums.end());
 
        // 2. 双指针
        int ret = 0, n = nums.size();
        for(int i = n-1; i >= 2; i--)// 固定最大的数，因为是三元组，从2开始
        {
            // 利用双指针统计出符合要求的三元组的个数
            int left = 0, right = i - 1;
            while (left < right)
            {
                if (nums[left]+nums[right] > nums[i])
                {
                    ret += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return ret;
    }
};