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

1. 题目

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

2. 示例

3. 分析 

题目有说明为递增数组，所以可以利用单调性+双指针解决。跟611. 有效的三角形个数为一类题目。

解题方法：

先定义两个指针指向数组左右，它们的和有三种情况：

• sum > target
  price[right]为数组内的最大值，price[left]为最小，所以此时[left+1, right-1]这个区间的数分别加上price[right]的和是肯定会超过target的，因为题目已经说明数组为递增的，最小加上最大都大于target，所以price[left] (最小)右边区间的数也肯定会大于target了。所以直接舍弃掉此时的最小值，再left++即可。
• sum < target
  price[right]为数组内的最大值，price[left]为最小，所以此时[left+1, right-1]这个区间的数分别加上price[left]的和是肯定不会超过target的，因为题目已经说明数组为递增的，最小加上最大都没有大于target，所以price[right] (最大)左边区间的数也肯定会小于target了。所以直接舍弃掉此时的最大值，再right--即可。
• sum == target
  返回结果即可

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left = 0, 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};// 题目莫得要求无结果需返回什么，所以随便返回两个负数即可}
};