【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品

简介: 【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品

1.题目


LCR 179. 查找总价格为目标值的两个商品


购物车内的商品价格按照升序记录于数组 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*

2. 解法⼀(暴⼒解法,会超时):



1.算法思路:

两层 for 循环列出所有两个数字的组合,判断是否等于⽬标值。

算法流程:

两层 for 循环:

◦ 外层 for 循环依次枚举第⼀个数 a ;

◦ 内层 for 循环依次枚举第⼆个数 b ,让它与 a 匹配;

ps :这⾥有个魔⻤细节:我们挑选第⼆个数的时候,可以不从第⼀个数开始选,因为 a 前

⾯的数我们都已经在之前考虑过了;因此,我们可以从 a 往后的数开始列举。

◦ 然后将挑选的两个数相加,判断是否符合⽬标值。


2.图解

image.png


3. 代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; i++) { // 第⼀层循环从前往后列举第⼀个数
            for (int j = i + 1; j < n;
                 j++) { // 第⼆层循环从 i 位置之后列举第⼆个数 
                if (nums[i] + nums[j] ==target) // 两个数的和等于⽬标值,说明我们
                    //已经找到结果了
                     return {nums[i], nums[j]};
            }
        }
        return {-1, -1};
    }
};

image.png

3. 解法⼆(双指针-对撞指针):


1.算法思路:


注意到本题是升序的数组,因此可以⽤「对撞指针」优化时间复杂度。

算法流程(附带算法分析,为什么可以使⽤对撞指针):

a. 初始化left , right 分别指向数组的左右两端(这⾥不是我们理解的指针,⽽是数组的下标)

b. 当 left < right 的时候,⼀直循环

i. 当 nums[left] + nums[right] == target 时,说明找到结果,记录结果,并且返回;

ii. 当 nums[left] + nums[right] < target 时:

• 对于 nums[left] ⽽⾔,此时 nums[right] 相当于是nums[left] 能碰到的最⼤值(别忘了,这⾥是升序数组哈~)。如果此时不符合要求,说明在这个数组⾥⾯,没有别的数符合 nums[left] 的要求了(最⼤的数都满⾜不了你,你已经没救了)。因此,我们可以⼤胆舍去这个数,让 left++ ,去⽐较下⼀组数据;

• 那对于 nums[right] ⽽⾔,由于此时两数之和是⼩于⽬标值的, nums[right] 还可以选择⽐nums[left] ⼤的值继续努⼒达到⽬标值,因此 right 指针我们按兵不动;

 iii. 当 nums[left] + nums[right] > target 时,

同理我们可以舍去nums[right] (最⼩的数都满⾜不了你,你也没救了)。让 right-- ,继续⽐较下⼀组数据,⽽ left 指针不变(因为他还是可以去匹配⽐ nums[right] 更⼩的数的)。


2.图解

image.png                                                                                                            

                                                                                                 

3.代码实现

image.png

此时我们需要    


// 照顾编译器
 return {-4941, -1};

           

1.C语言  

时间复杂度为O(n),空间复杂度为O(1)


int* twoSum(int* price, int priceSize, int target, int* returnSize){
    int left = 0;
    int right = priceSize - 1;
    *returnSize = 2;
    int *ret = (int*)malloc(*returnSize * sizeof(int));
    while (left < right)
     {
         int sum=price[left] + price[right];
        if ( sum == target) {
            ret[0] = price[left];
            ret[1] = price[right];
            return ret;
        } else if ( sum > target) {
            right--;
        } else {
            left++;
        }
    }
    return NULL;
}

image.png


2.C++    

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target)
    {
int left = 0, right = price.size() - 1;
        while (left < right) {
            int sum = price[left] + price[right];
            if (sum > target)
                right--;
            else if (sum < target)
                left++;
            else
                return {price[left], price[right]};
        }
        // 照顾编译器
        return {-4941, -1};
    }
};

image.png

相关文章
|
16天前
|
算法 数据挖掘 数据安全/隐私保护
基于CS模型和CV模型的多目标协同滤波跟踪算法matlab仿真
本项目基于CS模型和CV模型的多目标协同滤波跟踪算法,旨在提高复杂场景下多个移动目标的跟踪精度和鲁棒性。通过融合目标间的关系和数据关联性,优化跟踪结果。程序在MATLAB2022A上运行,展示了真实轨迹与滤波轨迹的对比、位置及速度误差均值和均方误差等关键指标。核心代码包括对目标轨迹、速度及误差的详细绘图分析,验证了算法的有效性。该算法结合CS模型的初步聚类和CV模型的投票机制,增强了目标状态估计的准确性,尤其适用于遮挡、重叠和快速运动等复杂场景。
|
20天前
|
算法 数据安全/隐私保护 索引
基于GWO灰狼优化的多目标优化算法matlab仿真
本程序基于灰狼优化(GWO)算法实现多目标优化,适用于2个目标函数的MATLAB仿真。使用MATLAB2022A版本运行,迭代1000次后无水印输出结果。GWO通过模拟灰狼的社会层级和狩猎行为,有效搜索解空间,找到帕累托最优解集。核心步骤包括初始化狼群、更新领导者位置及适应值计算,确保高效探索多目标优化问题。该方法适用于工程、经济等领域复杂决策问题。
|
5月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
66 0
|
4月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
5月前
|
机器学习/深度学习 人工智能 算法
【MM2024】面向 StableDiffusion 的多目标图像编辑算法 VICTORIA
阿里云人工智能平台 PAI 团队与华南理工大学合作在国际多媒体顶级会议 ACM MM2024 上发表 VICTORIA 算法,这是一种面向 StableDiffusion 的多目标图像编辑算法。VICTORIA 通过文本依存关系来修正图像编辑过程中的交叉注意力图,从而确保关系对象的一致性,支持用户通过修改描述性提示一次性编辑多个目标。
|
5月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
56 2
|
7月前
|
SQL 算法 Serverless
B端算法实践问题之使用concat_id算子获取用户最近点击的50个商品ID如何解决
B端算法实践问题之使用concat_id算子获取用户最近点击的50个商品ID如何解决
50 1
|
7月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
92 6
|
7月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
76 1
|
7月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
101 1