每日一题: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天前
leetcode-SQL-1795. 每个产品在不同商店的价格
leetcode-SQL-1795. 每个产品在不同商店的价格
34 0
|
7月前
【Leetcode -733.图像渲染 -744.寻找比目标字母大的最小字母】
【Leetcode -733.图像渲染 -744.寻找比目标字母大的最小字母】
25 0
|
3天前
代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零
代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零
35 0
|
3天前
leetcode-1475:商品折扣后的最终价格
leetcode-1475:商品折扣后的最终价格
29 0
|
3天前
leetcode-zj-future04:门店商品调配
leetcode-zj-future04:门店商品调配
16 0
|
3天前
|
SQL
leetcode-SQL-1549. 每件商品的最新订单
leetcode-SQL-1549. 每件商品的最新订单
20 0
|
3天前
|
Go
golang力扣leetcode 494.目标和
golang力扣leetcode 494.目标和
32 0
|
6月前
|
算法 测试技术 容器
代码随想录算法训练营第四十二天 | LeetCode 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零
代码随想录算法训练营第四十二天 | LeetCode 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零
29 1
|
7月前
【Leetcode -1475.商品折扣后的最终价格 -1544.整理字符串】
【Leetcode -1475.商品折扣后的最终价格 -1544.整理字符串】
30 0