【算法|双指针系列No.5】leetcode611. 有效三角形的个数

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

1️⃣题目描述

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

注意：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

2️⃣算法分析

首先判断是一个三角形的条件这里就不多多解释了。这里有一个简便的方法来判断是否为三角形：
如果a <= b <= c，此时我们如果知道a + b 是否 > c，满足三角形则是三角形，不满足则不是三角形的判断条件。

所以我们必须先对整个数组进行升序排序。

如果满足条件，就将r-l的差值加到结果ret中，并将右指针r向左移动一位。如果不满足条件，就将左指针l向右移动一位。这样可以找到所有满足条件的组合，统计其个数。

3️⃣代码编写

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int ret = 0,n = nums.size();
        for(int i = n - 1;i >= 2;i--)
        {
            int l = 0,r = i - 1;
            while(l < r)
            {
                if(nums[l] + nums[r] > nums[i]) ret += r - l,r--;
                else l++;
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17