深圳网页制作推广公司排名,seo知识点,哈尔滨建设工程交易中心,网站开发 基础教学视频个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣算法分析3️⃣代码编写 1️⃣题目描述
购物车内的商品价格按照升序记录于数组 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
2️⃣算法分析
本题目使用双指针的思想来进行解决
有两个指针l、r分别指向这个升序数组的两边
if(price[l] price[r] target)则r--else if(price[l] price[r] target)则l否则就返回此时两个指针指向的值即return {price[l],price[r]}
本题目的思想和leetcode611. 有效三角形的个数思路基本一致。可以对比进行理解。
3️⃣代码编写
class Solution {
public:vectorint twoSum(vectorint price, int target) {int n price.size();int l 0, r n - 1;while(l r){if(price[l] price[r] target) r--;else if(price[l] price[r] target) l;else return {price[l],price[r]};}return {-1,-1};}
};最后就是代码通过啦
