本文主要是介绍有效三角形个数问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一·题目简述：
二·思路总结：
2·1不被认可的暴力破解思路：
2·2优化后的思路：
2·2·1优化后的判断三角形方法：
2·2·2 定一动二指针朝内筛选遍历：
三·解答代码：
一·题目简述：
leetcode链接：. - 力扣（LeetCode）
二·思路总结：
2·1不被认可的暴力破解思路：
想必大家看到这道题首先一定想的就是三次循环嵌套，然后再加上判断三角形（任意两边都大于第三步）来完成此操作。伪代码：
for (int i = 0; i < nums.size()-2; i++) {for (int j = i + 1; j < nums.size() - 1; j++){for (int k = j + 1; k < nums.size(); k++) {check_triangle(nums[i], nums[j],nums[k])//判断是否为三角形}}
}然而这种复杂度直接到了o（n^3）；因此要换一种思路。
2·2优化后的思路：
2·2·1优化后的判断三角形方法：
想必正常都是 要么任意两边都大于第三步，要么两边差小第三边，两边和大第三边。
但是这种就是新的方法：如果我们把这组数据排好序，拿到最大的数，然后让比它小两个数之和跟它比较，便可以一步得出：
2·2·2 定一动二指针朝内筛选遍历：
思路：固定最大值+双指针筛选朝里遍历：
为了减少判断三角形（任意两边都大于第三边），升级版：首先让数组内值有序，然后只需要判断另两个值是否大于最大值即可，如果大于
就是符合，否则不符合，然后固定数前面的，
如果大于：最小值前面的与它组合都会大于，故right--(此时right这个位置的数已完成了此次任务)
如果小于：则最小值加上此值前面比它小的值，然后都比它小故left++下面画图展示一下：
此时时间复杂度直接从o（n^3）变成了o（n^2）。
三·解答代码：
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end(),less<int>());//按升序，方便减少判断三角形时的比较操作int ret=0;//统计个数for(int i=nums.size()-1;i>=2;i--){//固定的最大值从右往左走int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]) ret+=right-left,right--;//符合三角形条件else left++;}}return ret;}
};这篇关于有效三角形个数问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
