双指针算法专题
611. 有效三角形个数
题目描述
给定一个包含非负整数的数组，求其中可以组成三角形的三元组个数。
实现核心及思路
构成三角形的条件：设三角形三边长分别为 a（最长边），b（最短边），c。则有 a + b > c。
通过对三角形三边关系的分析，问题就是怎样找到三角形的最长边和最短边。解决这个问题：
我们可以先将数组元素进行排序（升序），让其满足单调性。每次固定最大值为第三边，最左边元素作为最短边，次最大值作为最长边，让最短边和最长边求和并与第三边比较。
解题步骤
- 排序（升序），降序也可。
- 从右往左将数组元素依次作为第三边；让左指针 left 指向最左侧元素，作为最短边；右指针 right 指向第三边左侧第一个元素，作为最长边。
- 注意：由于需要三个边构成三角形，则第三边最多为数组的第三个元素（nums[2]）。
- 最短边与最长边求和并与第三边比较。
- 注意：由于已经按照升序排序，只要 nums[left] + nums[right] > 第三边，说明只要将左侧元素作为最短边均满足要求，则此时有满足要求的 right - left 个三角形（更新结果），然后 right--，因为 nums[left] + nums[right--] 仍有可能满足要求；
- 如果 nums[left] + nums[right] <= 第三边，则只有让 left++，才有可能让最短边与最长边之和大于第三边（right--只能让两者之和更小）。
- 结束条件：right >= left。
代码实现
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 升序排序
int count = 0; // 记录三角形个数
// 从右往左依次将最大值作为第三边
for(int i = nums.size()-1; i >= 2; i--) {
int left = 0; // 左指针（最短边）
int right = i-1; // 右指针（最长边）
while(left < right) {
if(nums[left] + nums[right] > nums[i])
{
count += right-left;
right--;
}
left++;
}
}
count;
}
};
