链接:LCR 179. 查找总价格为目标值的两个商品 - 力扣(LeetCode)
LCR 179.查找总价格为目标值的两个商品
购物车内的商品价格按照升序记录于数组 price
。请在购物车中找到两个商品的价格总和刚好是 target
。若存在多种情况,返回任一结果即可。
示例 1:
输入:price = [3, 9, 12, 15], target = 18 输出:[3,15] 或者 [15,3]
示例 2:
输入:price = [8, 21, 27, 34, 52, 66], target = 61 输出:[27,34] 或者 [34,27]
提示:
1 <= price.length <= 10^5
1 <= price[i] <= 10^6
1 <= target <= 2*10^6
题解:
算法原理:利用单调性,左右双指针
代码:
class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {// 前后指针int n = price.size();int left = 0, right = n - 1;// 利用单调性for( ; price[left] + price[right] != target; ){if(price[left] + price[right] < target)left++;else if(price[left] + price[right] > target)right--;elsebreak;}// 定义一个int数组sum,插入两个值vector<int> sum;sum.push_back(price[left]);sum.push_back(price[right]);return sum;}
};