L39.【LeetCode题解】有效三角形的个数 (双指针思想)

本文链接：https://blog.csdn.net/2401_85828611/article/details/147015896

1.题目

https://leetcode.cn/problems/valid-triangle-number/description/

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

示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
(注:虽然2,3,4是重复的,但仍然要计入)
示例 2:
输入: nums = [4,2,3,4]
输出: 4
提示:

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

2.分析

方法1:暴力解法

三层循环,枚举所有三条边的组合,满足"任意两边之和大于第三边",计数器++

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        int count=0;
        for (int i=0;i<nums.size();i++)
        {
            for (int j=i+1;j<nums.size();j++)
            {
                for (int k=j+1;k<nums.size();k++)
                    //"任意两边",需要使用&&
                    if ((nums[i]+nums[j]>nums[k])&&
                        (nums[i]+nums[k]>nums[j])
                        &&(nums[j]+nums[k]>nums[i]))
                        count++;
            }
        }
        return count;
    }
};

时间复杂度为 $O(N^3)$ ,显然数据量大的情况下会超时

提交结果:

方法2:优化方法:先让数组有序,利用数组的单调性

反思方法1存在的问题:

if判断中有三个条件,需要判断三次,计算次数为 $T(3N^3)$ ,实际上在特殊的条件下,是否能构成三角形只需要一个条件:如果两个较小的数之和大于第三个数成立,就能构成三角形

例如有序数组[a,b,c]中 $a\leq b \leq c$ ,如果 $a+b> c$ ,则能构成三角形

由上述分析可知:可以先对数组进行排序,之后依据有序数组的单调性减小时间复杂度

版本1:原三重循环的改造

先对数组排序,之后使用原来的三重循环,只不过在一个一个枚举的时候,有些情况可以提前结束内循环:因为i,j,k是从小到大变化的,因此当nums[i]+nums[j]>nums[k]时,提前结束对k的循环,节省时间

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        int count=0;
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size();i++)
        {
            for (int j=i+1;j<nums.size();j++)
            {
                for (int k=j+1;k<nums.size();k++)
                    if (nums[i]+nums[j]>nums[k])
                        count++;
                    else
                        break;
            }
        }
        return count;
    }
};

提交结果:

版本2:双指针之左右指针(★推荐★)

需要将三个指针left、right和bound的其中一个固定下来,才能用双指针解决问题

以排过序的数组{2,2,3,4,5,9,10}为例,bound从右向左移动,先固定bound,讨论left和right的移动方法

因为是左右指针,则设left和right的初始值分别为0和bound-1,如下图:

发现nums[left]+nums[right]==2+9>nums[bound],则可以推出:

left向右移动时,均满足nums[left]+nums[right]==2+9>nums[bound]

一共有right-left个情况满足,此时不用循环,直接 count+=right-left后让right--,讨论下一次情况,直到left>right时,让bound--:

从上方的图可以看出:bound的最小值取2

代码如下:

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

提交结果: