查找总价格为目标值的两个商品原题地址
方法一:双指针
这道题和力扣第一题“两数之和”非常像,区别是这道题已经把数组排好序了,所以不考虑暴力枚举和哈希集合的方法,而是利用单调性,使用双指针求解。
考虑数组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 {};
}
};