双指针算法专题之——有效三角形的个数

文章目录题目介绍思路分析AC代码题目介绍链接: 611. 有效三角形的个数思路分析如果判断三个数能否构成一个三角形相信大家都知道只要任意两边之和大于第三边即可。比如三条边长度为abc那只要满足abcacbbca但是这样要判断三个条件我们来介绍另一种方法如果三条边的长短已经知道abc那么此时只需满足较短的两条边之和大于最长的那条边即abc那么它们就一定能构成一个三角形另外两个条件就不需要判断了原理很简单因为c是最大的c一个数一定比另外两条边还大。那题目呢是给定一个包含非负整数的数组 nums 要返回其中可以组成三角形三条边的三元组个数。所以判断的时候我们可以先给数组排个序升序然后呢我们就可以用双指针来解决这道题具体怎么做呢我们来看一个例子给这样一个数组最大值是10所以我们先让固定c为10那ab呢一个指向剩余区间的最大值一个指向最小值然后判断此时的ab11当然大于10第一种情况abc所以当前这一组是满足的可以构成三角形。然后我们观察此时a是最小的所以此时ab之间的数据都是a的所以中间的这些数据和b相加一定都大于此时的c。一共几种呢就是b的下标-c的下标当前情况下就是5-05种。所以中间的情况就不用判断了。b9时一共5种情况可行。假设两个指针left和right分别指向ab那接下来只需让right--即可判断c10b5时候的情况此时abc第二种情况abc所以构不成三角形并且可以断定此时a和ab之间的数都相加都不大于c因为这些数都比此时的b5小所以固定c为10的情况下a2时跟2 3 4 5都不行9已经判断过了所以此时让left看后面的行不行后面的数一定2因为已经排序后序也是如此进行判断。这一轮结束后当leftright结束固定c为10的情况就计算完了只需让c指向9right从c的前面开始left还从0下标开始进重复上述操作行下一轮的判断即可。总结一下先固定c为最大的数定义双指针按照上述逻辑判断出当前情况下符合条件的三元组个数。如果abcb前面的元素个数就是b为当前值的情况下符合条件的三元组个数然后b往前移right- -如果abc说明a为当前值的情况下找不到满足条件的让a往后移left再重新判断固定c为次大的数重复上述操作当c前面的数小于2个就结束了即c的下标2AC代码classSolution{public:inttriangleNumber(vectorintnums){sort(nums.begin(),nums.end());intindex_cnums.size()-1;//c的下标intcount0;while(index_c2)//index_c2此时左边的数就不够两个了{intleft0;//标识a的位置intrightindex_c-1;//b的位置while(leftright){if((nums[left]nums[right])nums[index_c]){count(right-left);--right;}elseleft;}--index_c;}returncount;}};