查找总价格为目标值的两个商品原题地址

方法一：双指针

这道题和力扣第一题“两数之和”非常像，区别是这道题已经把数组排好序了，所以不考虑暴力枚举和哈希集合的方法，而是利用单调性，使用双指针求解。

考虑数组 price 的 2 个下标 left 和 right ，对于 [left,right] ，有  种配对方法，我们需要利用单调性剔除一些可能。

不妨设 price[left]+price[right]<target ，考虑 [left+1,right-1] 范围内的下标（记为 m ），有 price[left]+price[m]<price[left]+price[right]<target ，所以 left 不可能与 [left+1,right] 的任何下标配对，此时让 left 右移，在 [left+1,right] 的范围内寻找配对。同理，若 price[left]+price[right]>target ，考虑 right 和 [left+1,right-1] 范围内的下标（记为 n ），有 price[right]+price[n]>price[right]+price[left]>target ，所以 right 不可能与 [left,right-1] 的任何下标配对，此时让 right 左移，在 [left,right-1] 的范围内寻找配对。

反复执行上述操作，直到 left=right 或者找到符合 price[left]+price[right]=target 的配对。

// 方法一：双指针
class Solution
{
public:vector<int> twoSum(vector<int>& price, int target){int left = 0, right = price.size() - 1;while (left < right){if (price[left] + price[right] < target){++left;}else if (price[left] + price[right] > target){--right;}else{return { price[left], price[right] };}}return {};}
};

方法二：哈希表

如果数组没有排好序呢？参考【力扣】两数之和，暴力枚举 + 哈希表的思路，其中暴力枚举会超时，这里附上本题的哈希表解法。

// 方法二：哈希表（适用于数组未排序的情况）
class Solution
{
public:vector<int> twoSum(vector<int>& price, int target){unordered_set<int> us;for (int i = 0; i < price.size(); ++i){// 哈希表中有元素与之匹配auto it = us.find(target - price[i]);if (it != us.end()){return { *it, price[i] };}// 存入哈希表us.insert(price[i]);}return {};}
};