1. 題目鏈接：LCR 179. 查找總價格為目標(biāo)值的兩個商品

2. 題目描述：

商品價格按照升序記錄于數(shù)組 price。請在購物車中找到兩個商品的價格總和剛好是 target。若存在多種情況，返回任一結(jié)果即可。

示例 1：

輸入：price = [3, 9, 12, 15], target = 18
輸出：[3,15] 或者 [15,3]

示例 2：

輸入：price = [8, 21, 27, 34, 52, 66], target = 61
輸出：[27,34] 或者 [34,27]

提示：

• 1 <= price.length <= 10^5
• 1 <= price[i] <= 10^6
• 1 <= target <= 2*10^6

3. 暴力枚舉（超時）

3.1 算法思路

用兩層循環(huán)把所有的可能性都列舉出來，然后判斷是否有等目標(biāo)值的兩個數(shù)

3.2 算法流程

1. 外層循環(huán)枚舉第一個數(shù)
2. 內(nèi)層循環(huán)枚舉第二個數(shù)，與第一個進(jìn)行匹配
3. 如果兩個數(shù)相加等于目標(biāo)值，返回這兩個數(shù)

3.3 C++算法代碼

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        for(int i=0;i<price.size();i++)
        {
            for(int j=i+1;j<price.size();j++)
            {
                if(price[i]+price[j]==target)
                {
                    return {price[i],price[j]};
                }
            }
        }
        return{-1,-1};
    }
};

4. 雙指針

4.1 算法思路

因為本題是升序的數(shù)組，利用對撞指針可以極大的優(yōu)化時間復(fù)雜度

4.2 算法流程

1. 初始化left和right分別指向數(shù)組的左右兩端（這里的left和right表示是下標(biāo)）

2. 當(dāng)left<right,進(jìn)入循環(huán)

   • 當(dāng)price[left]+price[right]==target，說明找到結(jié)果，記錄結(jié)果，并且返回

   • 當(dāng)price[left]+price[right]>target時，對于price[right]，此時price[left]相當(dāng)于price[right]能碰過的最小值，如果此時沒有符合price[right]的數(shù)了,right--然后比較下一組數(shù)據(jù)

   • 當(dāng)price[left]+price[right]<target時，對于price[left]，此時price[right]相當(dāng)于price[left]能碰過的最大值，如果此時就沒有符合price[left]的數(shù)了，left++然后比較下一組數(shù)據(jù)

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

4.3 C++算法代碼

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int n=price.size();
        //設(shè)置左右指針
        int left=0,right=n-1;
        while(left<right)
        {
            //大于右指針--
            if(price[left]+price[right]>target)
            right--;
            //小于左指針++
            else if(price[left]+price[right]<target)
            left++;
            else
            //返回
            return{price[left],price[right]};
        }
        return{-1,-1};
    }
};

到了這里，關(guān)于Leetcode算法解析——查找總價格為目標(biāo)值的兩個商品的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！