每日一题：LeetCode-LCR 179. 查找总价格为目标值的两个商品

每日一题系列（day 16）

前言：

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂，那么它的灵魂一定是👉👉算法👈👈，因此，想要写出💚优美的程序💚，核心算法是必不可少的，少年，你渴望力量吗😆😆，想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇，我们要做的，就是斩妖除魔💥💥，打怪升级！💪💪当然切记不可😈走火入魔😈，每日打怪，拾取经验，终能成圣🙏🙏！开启我们今天的斩妖之旅吧！✈️✈️

题目：

  购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例：

提示：

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

思路：

  首先最先想到的肯定是暴力解法，这道题暴力解法很简单，暴力枚举即可，时间复杂度是 O(n^2)。

  这里我们可以采用双指针来解决这道题，一个左指针left指向数组0位置处，一个右指针right指向数组最后一个元素下标。而要与target值进行比较，这里有三种情况，一种是大于target值，一种是小于target值，最后就是等于target值。

  1、首先，这是一个升序数组，当左右指针指向的值相加小于target值，左指针就自增，向后移动，因为是一个升序数组，所以 左指针向后移动才会可能等于target值。

  2、当左右指针指向的值相加大于targe值，这个时候在向右移动左指针就只会更大，所以这个时候我们移动右指针，控制 右指针向左移动。

  3、两个数刚好相等，那么就返回他们两个的值即可。如果遍历完了整个数组却没有合适的值，那么就返回0个元素的集合即可。

代码实现：

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

  其实经过前面这些题的练习，这题的双指针是很容易就想到的，左右位置的值相加进行比较，再做出对应的行为。