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

zhangcoder

已于 2025-05-08 17:08:15 修改

阅读量1k

点赞数 26

分类专栏： LeetCode题解 # 双指针文章标签： leetcode 算法 c++ 双指针

于 2025-04-12 19:36:43 首次发布

本文链接：https://blog.csdn.net/2401_85828611/article/details/147118037

版权

LeetCode题解同时被 2 个专栏收录

55 篇文章

订阅专栏

双指针

9 篇文章

订阅专栏

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;
    }
};

时间复杂度为 $O(N^2)$ ,显然数据量较大的情况下会超时

方法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代码有可以优化的空间吗?

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

当 $price[right]\geq target$ 时,是不用讨论的,因此可以先找到 $price[right]< target$ 时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向中间靠近,时间复杂度为 $O(N)$

提交结果:

当然版本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--;
            else
                left++;
        }
        return {};
    }
};

提交结果:

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

JZ57 和为S的两个数字

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

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

★2.传的数组可以为空(这个容易忽略), $0\leq len(array)\leq 10^5$ ,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--;
            else
                left++;
        }
        return {};
    }
};

提交结果: