1. 题目链接:LCR 179. 查找总价格为目标值的两个商品
2. 题目描述:
商品价格按照升序记录于数组
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
3. 暴力枚举(超时)
3.1 算法思路
用两层循环把所有的可能性都列举出来,然后判断是否有等目标值的两个数
3.2 算法流程
- 外层循环枚举第一个数
- 内层循环枚举第二个数,与第一个进行匹配
- 如果两个数相加等于目标值,返回这两个数
3.3 C++算法代码
class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {for(int i=0;i<price.size();i++){for(int j=i+1;j<price.size();j++){if(price[i]+price[j]==target){return {price[i],price[j]};}}}return{-1,-1};}
};
4. 双指针
4.1 算法思路
因为本题是升序的数组,利用对撞指针可以极大的优化时间复杂度
4.2 算法流程
-
初始化
left
和right
分别指向数组的左右两端(这里的left
和right
表示是下标) -
当
left<right
,进入循环-
当
price[left]+price[right]==target
,说明找到结果,记录结果,并且返回 -
当
price[left]+price[right]>target
时,对于price[right],此时price[left]相当于price[right]能碰过的最小值,如果此时没有符合price[right]的数了,right--
然后比较下一组数据 -
当
price[left]+price[right]<target
时,对于price[left]
,此时price[right]
相当于price[left]
能碰过的最大值,如果此时就没有符合price[left]
的数了,left++
然后比较下一组数据
-
4.3 C++算法代码
class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int n=price.size();//设置左右指针int left=0,right=n-1;while(left<right){//大于右指针--if(price[left]+price[right]>target)right--;//小于左指针++else if(price[left]+price[right]<target)left++;else//返回return{price[left],price[right]};}return{-1,-1};}
};