【双指针】：Leetcode611.有效三角形的个数-Toy模板网

这篇具有很好参考价值的文章主要介绍了【双指针】：Leetcode611.有效三角形的个数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

朋友们、伙计们，我们又见面了，本专栏是关于各种算法的解析，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

C 语言专栏：C语言：从入门到精通

数据结构专栏：数据结构

个人主页：stackY、

C + + 专栏：C++

Linux 专栏：Linux

【双指针】：Leetcode611.有效三角形的个数,初阶算法,leetcode,算法,职场和发展

1. 题目解析

2. 算法思路

3. 代码实现

4. 算法复杂度

1. 题目解析

Leetcode611.有效三角形的个数：https://leetcode.cn/problems/valid-triangle-number/

题目描述：

给定一个包含非负整数的数组 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

判断是否为三角形：两边之和大于第三边，首先想到的就是暴力求解，依次进行比较，但是这样的方法代价太高，根据有序的三个数判断是否能构成三角形，可以使用较小的两个数之和与较大的一个数进行比较，若成立，则能构成三角形。所以可以先对数组排序，再选取数据进行判断。

2. 算法思路

首先使用sort对数据进行有序处理

然后使用双指针算法再加上单调性进行判断：首先，确定一个最大值为max（第三条边），在max的左区间设置两个指针，left指向最右边的值，right指向最右边的值，判断left与right之和与max的大小，如果max大于它，由于right左边的值都比right小，所以right没必要--，所以只要让left++即可。

如果max小于它，由于left右边的值都比left大，所以left与right之间的数都可以与max组成三角形，所以只要让right--即可。

当left和right相遇时，再使用次大的作为第三条边，依次类推，直到整个数组只剩下三个元素，再判断最后一次就停止。

3. 代码实现

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //1.先排序
        sort(nums.begin(), nums.end());

        //2.确定第三条边，利用双指针依次判断比较
        int left, right;
        int Max = nums.size()-1;
        int count = 0;
        while(Max >= 2)      //剩下最后一组再判断一次即可
        {
            right = Max-1;
            left = 0;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[Max])
                {
                    count += (right - left);
                    right--;
                }
                else
                {
                    left++;
                }
            }
            Max--;  
        }
        return count;
    }
};

【双指针】：Leetcode611.有效三角形的个数,初阶算法,leetcode,算法,职场和发展