算法入门:剑指offer改编题目:查找总价格为目标值的两个商品

简介: 给定递增数组和目标值target,找出两数之和等于target的两个数字。利用双指针法,left从头、right从尾向中间逼近,根据和与target的大小关系调整指针,时间复杂度O(n),空间复杂度O(1)。找不到时返回{-1,-1}。

2057.png
查找总价格为目标值的两个商品

题目解析:

这个题我们可以看成是要找出来数组中两个相加等于target的数字。
输入一个递增排序的数组和一个数字s,也就是说数组中的数字是有序的,将数组中相加等于s的两个数字组合输出即可。

算法原理:

解法一暴力解法
暴力枚举策略:将数组中的所有组合都枚举出来,用两层for循环,伪代码展示:
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)这样做的不好处就是时间复杂度会上升。

解法二利用单调性,使用双指针算法解决问题

left放置在索引为0的位置,right放置在n-1的位置,这里给一个详细的例子数组[ 2 7 11 15 19 21 ],target为30,首先left是指向2的位置,right放置在21的位置,此时left+rightsum值小于target,最小的数字和最大的数字相加都小于target,那么就说明这个最小的数字跟其他数字相加也会小于target,利用单调性的知识我们可以明白,此时就是说left太小了,所以需要left++,换一个更大一点的数字进行相加的对比;所以将left指向7的位置,right指向21,相加还是小于target,接着让left指向11,让right指向21,相加此时发现大于target,也就是说此时的right太大了,让right--到下一个位置;此时left等于11,right=19,相加等于target,符合要求,返回即可。

下面我们就将思路转换为代码写出OJ题;

这道题目最后要让我们找出数组中两个相加等于target的数字,而且任意返回一对就好,我们用双指针算法解决这个问题,定义left=0,right=nums.size()-1;分别找到leftright的初始位置,接着定义一个sum存储相加之后的值,将sumtarget进行对比,

  • sum>target:说明right太大了,right--;
  • sum<target:说明left太小了,left++;
  • sum=target:返回nums[left],nums[right]

但是由于题目中没有给出一整个数组中都找不到两个相加等于target的数,原则上我们已经完成了题目的要求,但是提交代码的时候还会报错,所以要考虑一下编译器,最后我们任意返回两个值,假设编译器没有找到符合条件的值。return{-1,-1};大括号里可以是任意的值。

```class Solution {
public:
vector twoSum(vector& price, int target) {

    int left=0,right=price.size()-1;

    while(left<right)
    {
        int sum=price[left]+price[right];
        if(sum<target) left++;
        else if(sum>target) right--;
        else return {price[left],price[right]};
    }
   //并不是所有题目都有返回值,这里需要照顾一下编译器
   return{-1,-1};
}

};
```

相关文章
|
29天前
|
存储 算法
算法入门:专题二---滑动窗口(长度最小的子数组)类型题目攻克!
给定一个正整数数组和目标值target,找出总和大于等于target的最短连续子数组长度。利用滑动窗口(双指针)优化,维护窗口内元素和,通过单调性避免重复枚举,时间复杂度O(n)。当窗口和满足条件时收缩左边界,更新最小长度,最终返回结果。
|
1月前
|
存储 算法
算法入门:专题一:双指针(有效三角形的个数)
给定一个数组,找出能组成三角形的三元组个数。利用“两边之和大于第三边”的性质,先排序,再用双指针优化。固定最大边,左右指针从区间两端向内移动,若两短边之和大于最长边,则中间所有组合均有效,时间复杂度由暴力的O(n³)降至O(n²)。
|
26天前
|
机器学习/深度学习 数据采集 负载均衡
结合多种启发式解码方法的混合多目标进化算法,用于解决带工人约束的混合流水车间调度问题(Matlab代码实现)
结合多种启发式解码方法的混合多目标进化算法,用于解决带工人约束的混合流水车间调度问题(Matlab代码实现)
105 0
|
2月前
|
机器学习/深度学习 运维 算法
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
180 1
|
1月前
|
机器学习/深度学习 算法 物联网
基于遗传方法的动态多目标优化算法
基于遗传方法的动态多目标优化算法
|
2月前
|
机器学习/深度学习 存储 算法
【微电网调度】考虑需求响应的基于改进多目标灰狼算法的微电网优化调度研究(Matlab代码实现)
【微电网调度】考虑需求响应的基于改进多目标灰狼算法的微电网优化调度研究(Matlab代码实现)
135 0
|
26天前
|
机器学习/深度学习 算法 机器人
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
152 0
|
1月前
|
数据采集 分布式计算 并行计算
mRMR算法实现特征选择-MATLAB
mRMR算法实现特征选择-MATLAB
123 2
|
2月前
|
传感器 机器学习/深度学习 编解码
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
181 3
|
2月前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
114 6

热门文章

最新文章