Leetcode算法解析——查找总价格为目标值的两个商品-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode算法解析——查找总价格为目标值的两个商品。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目链接：LCR 179. 查找总价格为目标值的两个商品

2. 题目描述：

商品价格按照升序记录于数组 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

3. 暴力枚举（超时）

3.1 算法思路

用两层循环把所有的可能性都列举出来，然后判断是否有等目标值的两个数

3.2 算法流程

外层循环枚举第一个数
内层循环枚举第二个数，与第一个进行匹配
如果两个数相加等于目标值，返回这两个数

Leetcode算法解析——查找总价格为目标值的两个商品,算法,leetcode,算法,职场和发展

3.3 C++算法代码


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)
                {
                    return {price[i],price[j]};
                }
            }
        }
        return{-1,-1};
    }
};

4. 双指针

4.1 算法思路

因为本题是升序的数组，利用对撞指针可以极大的优化时间复杂度

4.2 算法流程

初始化left和right分别指向数组的左右两端（这里的left和right表示是下标）
当left<right,进入循环
- 当price[left]+price[right]==target，说明找到结果，记录结果，并且返回
- 当price[left]+price[right]>target时，对于price[right]，此时price[left]相当于price[right]能碰过的最小值，如果此时没有符合price[right]的数了,right--然后比较下一组数据
- 当price[left]+price[right]<target时，对于price[left]，此时price[right]相当于price[left]能碰过的最大值，如果此时就没有符合price[left]的数了，left++然后比较下一组数据

Leetcode算法解析——查找总价格为目标值的两个商品,算法,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/news/detail-725552.html

4.3 C++算法代码

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int n=price.size();
        //设置左右指针
        int left=0,right=n-1;
        while(left<right)
        {
            //大于右指针--
            if(price[left]+price[right]>target)
            right--;
            //小于左指针++
            else if(price[left]+price[right]<target)
            left++;
            else
            //返回
            return{price[left],price[right]};
        }
        return{-1,-1};
    }
};

到了这里，关于Leetcode算法解析——查找总价格为目标值的两个商品的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！