每日一题:LeetCode-LCR 179. 查找总价格为目标值的两个商品

简介: 每日一题:LeetCode-LCR 179. 查找总价格为目标值的两个商品

每日一题系列(day 16)

前言:

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,拾取经验,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️


题目:

  购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况,返回任一结果即可。

示例:

提示:

  • 1 <= price.length <= 10^5
  • 1 <= price[i] <= 10^6
  • 1 <= target <= 2*10^6

思路:

  首先最先想到的肯定是暴力解法,这道题暴力解法很简单,暴力枚举即可,时间复杂度是 O(n^2)

  这里我们可以采用双指针来解决这道题,一个左指针left指向数组0位置处,一个右指针right指向数组最后一个元素下标。而要与target值进行比较,这里有三种情况,一种是大于target值,一种是小于target值,最后就是等于target值。

  1、首先,这是一个升序数组,当左右指针指向的值相加小于target值,左指针就自增,向后移动,因为是一个升序数组,所以 左指针向后移动才会可能等于target值

  2、当左右指针指向的值相加大于targe值,这个时候在向右移动左指针就只会更大,所以这个时候我们移动右指针,控制 右指针向左移动

  3、两个数刚好相等,那么就返回他们两个的值即可。如果遍历完了整个数组却没有合适的值,那么就返回0个元素的集合即可。

代码实现:

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0, len = price.size();
        int right = len - 1;
        for(int i = 0 ; i < len ; i++)
        {
            if((price[left]+price[right]) < target)
            {
                left++;
            }
            else if((price[left]+price[right]) > target)
            {
                right--;
            }
            else
            {
                return {price[left], price[right]};
            }
        }
        return {};
    }
};


  其实经过前面这些题的练习,这题的双指针是很容易就想到的,左右位置的值相加进行比较,再做出对应的行为。

相关文章
|
3月前
|
Python
【Leetcode刷题Python】494. 目标和
LeetCode 494题 "目标和" 的Python解决方案,通过动态规划算法计算在给定整数数组和目标值的情况下,可以构造多少种不同表达式使得运算结果等于目标值。
40 3
|
6月前
|
算法
【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品
【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品
|
5月前
【LeetCode刷题】有效三角形个数、查找总价值为目标值的两个商品
【LeetCode刷题】有效三角形个数、查找总价值为目标值的两个商品
|
6月前
代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零
代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零
56 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
55 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
113 2
|
17天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
16 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
3月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
56 7