611. 有效三角形的个数（双指针）

文章目录

前言
一、题目解析
二、代码原理
- 1.暴力解法
- 2.双指针优化
三、代码编写
总结

前言

在本篇文章中，我们将会带着大家解决一下611. 有效三角形的个数这道题目，本道题木将会用双指针的方法解决。

一、题目解析

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:

输入: nums = [4,2,3,4]
输出: 4

🌟🌟题目是非常简单的，我们想一下三条边满足什么关系才能构成三角形

任意两条边之和大于第三边就可以

假设三个数a,b,c
要证明是三角形，我们需要判断
🌟a+b>c
🌟a+c>b
🌟b+c>a

二、代码原理

1.暴力解法

我们很容易想到暴力解法，一个个去试，三层for循环，时间复杂度为O(N^3),这个时间复杂度有点高。

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        int n=nums.size();
        if(n<3) return 0;
        int count=0;
        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])&&(nums[i]+nums[k]>nums[j])&&(nums[j]+nums[k]>nums[i]))
                    {
                        count++;
                    }
                }
            }
        }
        return count;

    }
};

我们能不能有所优化呢？？
我们的if需要判断三次，时间复杂度更准确来说是O（3*N^3）。

我们可以进行排序，这时我们就仅需要判断a+b>c就可以了（假设a<b<c）

2.双指针优化

我们本道题可以采用双指针来进行优化，因为我们已经排序了，同时根据分析满足单调性。

一个个数的固定

🌟先固定一个最大的数ret,在比这个数小的区间内找两个数。
🌟在剩下的区间内进行判断，left指向最左边元素，right指向最大数左边的那个元素
🌟如果left+right>ret,那么left和right之间的数就都满足这个条件，满足条件的有right-left个，我们就不用判断了，只需要将个数加上就行。再让right–.
🌟如果left+right<=ret，就说明构不成三角形，这时说明left位置的元素可以舍弃，left++;
🌟继续循环，将最大数改变，降为下一大的数。

三、代码编写

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        //先排序
        sort(nums.begin(),nums.end());
        int n=nums.size();
        if(n<3)return 0;
        int count=0;
        for(int i=n-1;i>=2;i--)
        {
            int ret=nums[i];
            int left=0;
            int right=i-1;
            while(left<right)
            {
                if(nums[left]+nums[right]>ret)
                {
                    count+=right-left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return count;
    }
};