算法基础学习Day3(双指针)

1.题目

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

2.题目解答

题目及题目解析

算法学习

解法一:暴力枚举

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

这里的时间复杂度是NlogN+N*3,虽然能过但是还是可以进行优化的

解法二:利用单调性,使用双指针解决问题

这个优化在排完序的基础上

1. **情况一:**能成为三角形

那么后面从left到right的数都可以组成三角形,直接将这部分的数组进行相加就行

中间的数据个数表达式:right-left

接着让right--

2. **情况二:**不能成为三角形

那么聪right开始到left的数都没办法组成三角形

直接让left++即可

总结来说,步骤如下:

1. 先固定最大的数
2. 用双指针算法快速求解

代码提交

写成代码如下:

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

原文地址：https://blog.csdn.net/2302_82004664/article/details/144318731

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！