LeetCode - LCR 179.查找总价格为目标值的两个商品

一. 题目链接

 LeetCode - LCR 179. 查找总价格为目标值的两个商品

解法（双指针 - 对撞指针）：

算法思路：

注意到本题是升序的数组，因此可以用「对撞指针」优化时间复杂度。

算法流程：

初始化left ，right 分别指向数组的左右两端（这里不是我们理解的指针，而是数组的下标），当left < right 的时候，⼀直循环

i. 当nums[left] + nums[right] == target 时：

• 说明找到结果，记录结果，并且返回；

ii. 当nums[left] + nums[right] < target 时：

• 对于nums[left]而言，此时nums[right] 相当是nums[left] 能碰到的最大值（别忘了，这是升序数组）。如果此时不符合要求，说明在这个数组里⾯， 没有别的数符合nums[left] 的要求了（最大的数都满足不了你，你已经没救了）。 因此，我们可以大胆舍去这个数，让left++ ，去比较下⼀组数据；
• 那对于nums[right]而言，由于此时两数之和是小于目标值的， nums[right] 还可以选择比nums[left]大的值继续努力达到目标值，因此right 指针我们按兵不动；

iii. 当nums[left] + nums[right] > target 时：

• 同理我们可以舍去，nums[right]（最小的数都满足不了你，你也没救了）。让right-- ，继续比较下⼀组数据，而left 指针不变（因为他还是可以去匹配比nums[right] 更小的数的）。

二. 动画解释 

三. 代码解释 

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