原题链接：611. 有效三角形的个数 - 力扣（LeetCode）
题目说，给定一个包含非负整数的数组 num，返回其中可以组成三角形三条边的三元组个数。
示例： nums = [4, 2, 3, 4]；
有效组合如下：
2，3，4 (使用第一个4)
2，3，4 (使用第二个4)
2，4，4
3，4，4
做题思路：
可能想到的第一种方案就是暴力枚举，枚举出所有的情况，比如下面的代码：
int sum = 0;
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
for (int k = j + 1; k < n; ++k)
{
if (IsValid(v[i], v[j], v[k])) ++sum;
}
}
}上面的暴力枚举的时间复杂度是 O(N^3)。 我们思考一下，能不能优化一下？
优化一：判断 a，b，c 三个数字能否构成一个合法三角形
首先，如果数据不是有序的，那么判断需要通过三次，即：
- a + b > c；
- a + c > b；
- b + c > a；
但如果此时数据是有序的，假如， a <= b <= c，那么此时判断能否构成一个合法三角形，只需要判断一次，即：
a + b > c；
而 a + c > b 和 b + c > a 不需要判断，因为此时c是最大的数据，最大的数据加上一个非负数，一定大于另外的一个数据，比如，a + c 是一定大于 b 的。
这是优化一。
优化二，我们想通过双指针 + 单调性的方案优化上面的问题，通过一个示例来理解一下：
假设数据为2，3，4，6，6，7，9，让我们来判断一下可以构成三角形的个数：
首先，我们固定一个值，然后判断，剩下的数字和这个固定值能构成的三角形个数是多少，比如，我们固定最大值为9，然后判断剩下的数据和这个9能构成的三角形个数是多少个，如图所示：
因为此时 a = 2， b = 7， c = 9，它们是有序的数据，故只需要判断一次：a + b > c，不成立，既然最小的 a 不能构成一个三角形，那么就让a向右移动，如下：
此时 a = 3，b = 7，c = 9，同理，只需要判断一次，a + b > c ， 成立，因为数据是有序的，而此时在 3 到 7 这个区间中，3 是最小的数据，那么4，6，6，毋庸置疑，也可以和 b = 7，c = 9 构成一个三角形， 故4，6，6， 不需要再判断，因此，当 c = 9，b = 7 时，能构成的三角形个数就等于b所在的下标 - a所在的下标，此时b = 7这种情况就讨论完了，因此，b 向左移动：
此时 a = 3， b = 6，c = 9， a + b > c，不成立，因此，a 向右移动：
a = 4， b = 6， c = 9，a + b > c，成立，因为在a到b这个区间中，a此时是最小的，而数据又是单调递增 (有序的)，因此，在 a 和 b 中间的值就不需要再判断了，此时一定可以和 b = 6，c = 9 构成三角形，因此，此时可以构成三角形的个数：b的下标 - a 的下标，b向左移动。
此时，和上述情况一样，可以构成三角的个数：b的下标 - a的下标 ，b向左移动：
a 和 b 相遇，c = 9 这种情况能构成的三角形的个数就讨论完了。此时，我们在固定一个值，即让c向左移动，让 c == 7，然后重复上述过程，如下所示：
此时，我们就可以将一组数据可以构成三角型的个数全部讨论清楚，可以发现，上面这个思路的时间复杂度：O(N^2)，因为c从最后一个数据开始，需要从后向前遍历数组(O(N))，而每一个c都需要让a和b一起遍历 (a向右移动，b向左移动) 数组，故也是O(N)，因此上面算法的时间复杂度为 O(N^2)，这就是通过单调性 + 双指针解决上述问题。
代码如下：
#include <iostream>
#include <vector>
class Solution {
public:
inline bool IsValid(int a, int b, int c)
{
return a + b > c;
}
int triangleNumber(std::vector<int>& nums) {
// 这里的 left 相当于a
// 这里的 right 相当于b
// 这里的 objpos 相当于c
// 它们都是数组下标
std::sort(nums.begin(), nums.end());
int objpos = nums.size() - 1;
int sum = 0;
while (objpos > 1)
{
int left = 0;
int right = objpos - 1;
while (left < right)
{
if (IsValid(nums[left], nums[right], nums[objpos]))
{
sum += (right - left);
right--;
}
else
{
left++;
}
}
objpos--;
}
return sum;
}
};
