怎么下载网站的视频,wordpress用户密码表,软文写作的三个要素,合肥快速建站模板1. 题目链接#xff1a;LCR 179. 查找总价格为目标值的两个商品
2. 题目描述#xff1a; 商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况#xff0c;返回任一结果即可。 示例 1#xff1a; 输入#xff1a;price …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^51 price[i] 10^61 target 2*10^6 3. 暴力枚举超时
3.1 算法思路
用两层循环把所有的可能性都列举出来然后判断是否有等目标值的两个数
3.2 算法流程
外层循环枚举第一个数内层循环枚举第二个数与第一个进行匹配如果两个数相加等于目标值返回这两个数 3.3 C算法代码 class Solution {
public:vectorint twoSum(vectorint price, int target) {for(int i0;iprice.size();i){for(int ji1;jprice.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表示是下标 当leftright,进入循环 当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:vectorint twoSum(vectorint price, int target) {int nprice.size();//设置左右指针int left0,rightn-1;while(leftright){//大于右指针--if(price[left]price[right]target)right--;//小于左指针else if(price[left]price[right]target)left;else//返回return{price[left],price[right]};}return{-1,-1};}
};
