L36.【LeetCode题解】查找总价格为目标值的两个商品(剑指offer:和为s的两个数字) (双指针思想,内含详细的优化过程)

目录

1.LeetCode题目

2.分析

方法1:暴力枚举(未优化的双指针)

方法2:双指针优化:利用有序数组的单调性

版本1代码

提问:版本1代码有可以优化的空间吗?

版本2代码

提问:版本2代码有可以优化的空间吗?

版本3代码(★推荐★)

3.牛客网题目:和为s的数字

---

1.LeetCode题目

https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/

购物车内的商品价格按照升序记录于数组 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^5
• 1 <= price[i] <= 10^6
• 1 <= target <= 2*10^6

2.分析

方法1:暴力枚举(未优化的双指针)

直接使用两个循环变量i和j,判断price[i]+price[j]是否等于target

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {for (int i=0;i<price.size();i++){for (int j=i+1;j<price.size();j++){if (price[i]+price[j]==target){vector<int> ret={price[i],price[j]};return ret;}}}//由于一定能找到符合要求的两个数字,程序不会执行到此处,所以这里随便返回一个数组vector<int> no_use;return no_use;}
};

时间复杂度为,显然数据量较大的情况下会超时

方法2:双指针优化:利用有序数组的单调性

和L35.【LeetCode题解】有效三角形的个数 (双指针思想)文章的解法类似,使用左右指针方法

以数据price = [8, 21, 27, 34, 52, 66], target = 61为例

初始情况:

发现8+66>61,为了让相加的结果变小,right--

发现8+52<61,此时让right再--已经没有意义,遂结束内循环,让left++,right重新回到数组末尾

发现21+66>61,为了让相加的结果变小,right--

 21+52>61,为了让相加的结果变小,right--

21+34<61,此时让right再--已经没有意义,遂结束内循环,让left++,right重新回到数组末尾

27+66>61,为了让相加的结果变小,right--

27+52>61,为了让相加的结果变小,right--

27+34==61,结束循环返回结果

版本1代码

class Solution {
public:vector<int> twoSum(vector<int>& price, int target){int right=price.size()-1;for (int left=0;left<right;left++){for (int i=right;i>left;i--){if (price[i]+price[left]>target){//什么都不做}else if (price[i]+price[left]==target){vector<int> ret={price[i],price[left]};return ret;}else//price[i]+price[left]<target{break;}}}//由于一定能找到符合要求的两个数字,程序不会执行到此处,所以这里随便返回一个数组vector<int> no_use;return no_use;}
};

提交结果:

提问:版本1代码有可以优化的空间吗?

有,从之前的讨论情况来看:

当时,是不用讨论的,因此可以先找到时right的最大取值,再做内外循环,能提高运行速度

同时可以删除if (price[i]+price[left]>target),当条件满足时没有要执行的操作

版本2代码

class Solution {
public:vector<int> twoSum(vector<int>& price, int target){int right=price.size()-1;for (;price[right]>=target;right--);//找到right的最大值  for (int left=0;left<right;left++){for (int i=right;i>left;i--){if (price[i]+price[left]==target){vector<int> ret={price[i],price[left]};return ret;}if (price[i]+price[left]<target){break;}}}//由于一定能找到符合要求的两个数字,程序不会执行到此处,所以这里随便返回一个数组vector<int> no_use;return no_use;}
};

left和right向中间靠近,时间复杂度为

提交结果:

当然版本2的代码在返回值上可以简写为如下代码:

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

使用return {...}来返回vector数组,这是C++11引入的初始化列表语法 

提问:版本2代码有可以优化的空间吗?

有,从之前的讨论情况来看,可以将二重循环降为一重循环

不用内循环的变量i

发现8+52<61,此时让right再--已经没有意义,让left++,此时right不用重新回到数组末尾,保持right的值不变

版本3代码(★推荐★)

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

提交结果:

3.牛客网题目:和为s的数字

JZ57 和为S的两个数字

和查找总价格为目标值的两个商品题目不同的是:

1.可能存在找不到的情况

★2.传的数组可以为空(这个容易忽略),,len(array)可以为0

对版本3的代码稍作调整即可

class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array,int sum) {if (array.size()==0)return {};int left=0;int right=array.size()-1;for (;array[right]>=sum;right--);while(left<right){if (array[left]+array[right]==sum)return {array[left],array[right]};else if (array[left]+array[right]>sum)right--;elseleft++;}return {};}
};

提交结果: