专题一_双指针_有效三角形的个数

一：题目解析

题目链接：611. 有效三角形的个数 - 力扣（LeetCode）

解析：任意两边之和大于第三边 or 任意两边之差小于第三边，所以选择任意一个条件即可，只需满足a+b>c 和 a+c>b 和 b+c>a 即可

二：算法讲解

①：暴力

暴力无非就是三层for循环，加判断函数，伪代码如下：

for(i=O;i<n;i++)//固定第一个数
for(j=i+1;j<n;j++)//固定第二个数
for(k=j + 1;k<n; k++)//固定第三个数
check(nums[i],nums[j] ,nums[k] )//函数判断是否能构成三角形

解析：时间复杂度为：3N^3也就是N^3，会超时！

Q：为什么前面有3

A：因为check这一步每次进入都要执行三次(三次比较a+b>c ； a+c>b ；b+c>a) 

②：优秀

所以对暴力进行优化一下！

优化1：升序对比较的优化

现在有abc，我们排升序后，得到a<=b<=c，此时仅仅需要取较小的两个数字 a b 
去判断a+b>c 即可，一但成立，则一定为三角形！

因为：如果a+b>c ，那么a+c>b 和 b+c>a这两个式子恒成立！c本来就大于b或a，还给c加上一个数，所以这两个式子是一定成立的 ！！

所以我们排序之后 只需比较一次即可！此时的时间复杂度为：NlogN(排序) + N^3

优化2：升序对三层循环的优化

形成有序后，我们可以对暴力中的三层for循环进行优化！ 让其的复杂度更低！
假设现在是：[2,2,3,4,5,9,10 ]，a(left) = 2；b(right) =9；c = 10，其中ab为两个指针，c先固定为最大的数字！

此时如果a+b>c了，此时不仅abc已经是有效三角形了，且我们a就不用再往后遍历到b的前一个了(a为2,3,4,5不用再遍历)！因为a+b 肯定都会>c(b在增加，肯定更能满足a+b>c)
所以我们的left指针不用移动，而是right指针从9变为5！

Q：为什么b从9变成5了 A：因为9的有效三元组全部收录！此时应该改变right指针，再去和left相加比较
此时2+5<10了，所以你的b也没必要向内枚举了(b只会越来越小)；而是让a向内枚举，直到遇到和b相加>c的时候！

此时的时间复杂度为：NlogN(排序) +N^2(双指针遍历)

总结：先将数组排序，让复杂度从N^3 变为了 NlogN+N^2

三：代码编写

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int ret = 0;//存储有效三元组的个数int n = nums.size();for (int c = n - 1; c >= 2; c--) {//c从最后一个遍历到第三个元素 因为三元组 你起码得给ab留两个吧int left = 0, right = c - 1;//确定双指针的位置while (left < right) {//双指针相遇 代表此趟的c已经判断完成 c--后 双指针再次遍历if (nums[left] + nums[right] > nums[c]) {//a+b>c 则a不用再遍历了ret += right - left;//双指针下标之差代表有效三元组的个数 让ret+=即可right--;//然后right--} elseleft++;///a+b不>c  则left++ 才有可能a+b>c}}return ret;}
};

解释：

1：c从最后一个遍历到第三个元素，因为三元组，你c最多只能移动到第三个元素，这样才能留两个值给双指针

2：当a+b>c的时候，此时双指针下标之差代表有效三元组的个数，本质是bc不变，a的可变值的种数