欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > 名人名企 > 【优选算法】查找总价格为目标值的两个商品(双指针)

【优选算法】查找总价格为目标值的两个商品(双指针)

2025/3/17 0:39:00 来源:https://blog.csdn.net/lrq13965748542/article/details/144829102  浏览:    关键词:【优选算法】查找总价格为目标值的两个商品(双指针)

算法_云边有个稻草人的博客-CSDN博客

目录

解法一:暴力算法

解法二:双指针(时间复杂度为O(N))

【代码编写】




LCR 179. 查找总价格为目标值的两个商品 - 力扣(LeetCode)

解法一:暴力算法

用两个for循环,列出所有的两个数的和进行判断,时间复杂度为O(N^2),不推荐。

算法流程:
两层 for 循环
外层 for 循环依次枚举第⼀个数 a
内层 for 循环依次枚举第⼆个数 b ,让它与 a 匹配;
ps :这⾥有个魔⻤细节:我们挑选第⼆个数的时候,可以不从第⼀个数开始选,因为 a 前⾯的数我们都已经在之前考虑过了;因此,我们可以从 a 往后的数开始列举。 然后将挑选的两个数相加,判断是否符合⽬标值。
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 };}
};

解法二:双指针(时间复杂度为O(N))

【代码编写】

class Solution 
{
public:vector<int> twoSum(vector<int>& price, int target) {int left = 0;int 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]};}//这里对于编译器,若没有值等于target要设置一个返回值,让所有的情况都有所返回return {-1,-1};}
};

完——

继续。。。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词