??

611. 有效三角形的個數(shù)

611.?有效三角形的個數(shù)https://leetcode.cn/problems/valid-triangle-number/

題目描述：

給定一個包含非負整數(shù)的數(shù)組?nums?，返回其中可以組成三角形三條邊的三元組個數(shù)。

解題思路：

本題是一個關(guān)于三角形是否能成立的題目，首先我們假設(shè)三角形的三邊（a，b,c），我們要保證兩邊之和大于第三邊

?

?題目給我們nums是亂序的，如果我們一個個abc去實驗就是會超時（時間復(fù)雜度O^3）

當我們將sort排序一下，這樣的話假設(shè)a<b<c的情況下，我們就只要去判斷a+b>c是否成立！

這里我們遍歷每個c（從后往前），這樣時間復(fù)雜度就變成了N^2+NlogN也就是N^2

解題代碼：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        //假設(shè)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的兩個數(shù)字

劍指 Offer 57.?和為s的兩個數(shù)字https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

題目描述：

輸入一個遞增排序的數(shù)組和一個數(shù)字s，在數(shù)組中查找兩個數(shù)，使得它們的和正好是s。如果有多對數(shù)字的和等于s，則輸出任意一對即可。

解題思路：?

首先本題是升序數(shù)組，這里如果我們用暴力的話會超時

這里我們使用雙指針，我們讓一個指向頭left一個指向尾right，這里left、right和target會有三種關(guān)系

我們假設(shè)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};
    }
};

?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-659118.html

到了這里，關(guān)于【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！