【优选算法】有效三角形的个数（双指针算法）

优质专栏：算法_云边有个稻草人的博客-CSDN博客

目录

【611. 有效三角形的个数 - 力扣（LeetCode）】

  解法一：

  解法二：

---

【611. 有效三角形的个数 - 力扣（LeetCode）】

  解法一：

三层for循环枚举出所有三元组，判读每组是否能构成三角形，会超时，但是我们可以再优化一下：先对数组进行排序，只需判断三元组中最小的两个数是否大于第三个数即可，省略有一些不必要的判断。

class Solution {
public:int triangleNumber(vector<int>& nums) {// 1. 排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;// 2. 从⼩到⼤枚举所有的三元组for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {// 当最⼩的两个边之和⼤于第三边的时候，统计答案if (nums[i] + nums[j] > nums[k])ret++;}}}return ret;}
};

  解法二：

时间复杂度为O(N)。 

class Solution 
{
public:int triangleNumber(vector<int>& nums) {//1.先对数组进行排序sort(nums.begin(),nums.end());//2.利用双指针解决问题int ret = 0,n = nums.size();for(int i = n-1;i>=2;i--)//固定最大的那个数{int left = 0,right = i-1;while(left < right){if((nums[left]+nums[right])>nums[i]){ret += right-left;right--;}elseleft++;}}return ret;}
};

完——

---

明天继续。。。