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 = 2; i--)// 固定最大的数，因为是三元组，从2开始 { // 利用双指针统计出符合要求的三元组的个数 int left = 0, right = i - 1; while (left nums[i]) { ret += right - left; right--; } else { left++; } } } return ret; } };
  
  （图片来源网络，侵删）