1. 題目

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

2. 示例

3. 分析?

題目有說明為遞增數(shù)組，所以可以利用單調(diào)性+雙指針解決。跟611. 有效的三角形個數(shù)為一類題目。

解題方法：

先定義兩個指針指向數(shù)組左右，它們的和有三種情況：

• sum > target
  price[right]為數(shù)組內(nèi)的最大值，price[left]為最小，所以此時[left+1, right-1]這個區(qū)間的數(shù)分別加上price[right]的和是肯定會超過target的，因為題目已經(jīng)說明數(shù)組為遞增的，最小加上最大都大于target，所以price[left] (最小)右邊區(qū)間的數(shù)也肯定會大于target了。所以直接舍棄掉此時的最小值，再left++即可。
• sum < target
  price[right]為數(shù)組內(nèi)的最大值，price[left]為最小，所以此時[left+1, right-1]這個區(qū)間的數(shù)分別加上price[left]的和是肯定不會超過target的，因為題目已經(jīng)說明數(shù)組為遞增的，最小加上最大都沒有大于target，所以price[right] (最大)左邊區(qū)間的數(shù)也肯定會小于target了。所以直接舍棄掉此時的最大值，再right--即可。
• sum == target
  返回結(jié)果即可

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};// 題目莫得要求無結(jié)果需返回什么，所以隨便返回兩個負數(shù)即可}
};