每日一题系列(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 {}; } };
其实经过前面这些题的练习,这题的双指针是很容易就想到的,左右位置的值相加进行比较,再做出对应的行为。