【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字-Toy模板网

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

【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字,算法挨揍日记,Leetcode,算法,职场和发展

611. 有效三角形的个数

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

题目描述：

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

【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字,算法挨揍日记,Leetcode,算法,职场和发展

解题思路：

本题是一个关于三角形是否能成立的题目，首先我们假设三角形的三边（a，b,c），我们要保证两边之和大于第三边

题目给我们nums是乱序的，如果我们一个个abc去实验就是会超时（时间复杂度O^3）

当我们将sort排序一下，这样的话假设a<b<c的情况下，我们就只要去判断a+b>c是否成立！

这里我们遍历每个c（从后往前），这样时间复杂度就变成了N^2+NlogN也就是N^2

解题代码：

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

剑指 Offer 57. 和为s的两个数字

剑指 Offer 57. 和为s的两个数字https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

题目描述：

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字,算法挨揍日记,Leetcode,算法,职场和发展

解题思路：

首先本题是升序数组，这里如果我们用暴力的话会超时

这里我们使用双指针，我们让一个指向头left一个指向尾right，这里left、right和target会有三种关系

我们假设sub=right-left

第一种情况很显然直接返回就好了我们来研究一下第二种和第三种情况：

解题代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        int left=0;
        int right=n-1;
        while(nums[right]>target)
        {
            right--;
        }
        while(left<right)
        {
            int sub=target-nums[right];
            if(sub==nums[left])
            {
                return {nums[left],nums[right]};
            }
            else if(sub>nums[left])
            {
                left++;
            }
            else//sub<nums[left]
            {
                right--;
            }
        }
        return {-1,-1};
    }
};

文章来源地址https://www.toymoban.com/news/detail-659118.html

到了这里，关于【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！