【双指针】有效三角形的个数

611. 有效三角形的个数

611. 有效三角形的个数

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

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

---

解题思路：排序+双指针

​ 和上一道题一样，如果使用暴力破解也就是枚举的话，此时会超时，所以我们就要换一种方式来解决！

​ 我们首先要知道能构成三角形的条件：两边之和大于第三边。但是因为这道题的数据是无序的，如果我们不用排序的话，可能会稍微麻烦一些，为什么呢，因为我们得判断三条边，两两组合是否都大于第三边才算是构成三角形，这不也和枚举差不多吗？

​ 但是如果我们先进行排序，将数组变成升序序列，这样子有什么好处❓❓❓

​ 这样子就能保证，大的边一定在后边，那我们只需要判断前面两个数是否大于第三个数，如果大于的话，反之用这个第三个数去和前面某一个数组合肯定也是大于另一个数的！这样子的话，我们只需要判断一次，并且不需要全部数据都去枚举！

​ 以下是算法步骤：

1. 首先对数组排升序

2. 固定最长的一条边，然后运用碰撞指针扫描两条边，大概是这样子：