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

算法_云边有个稻草人的博客-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};
    }
};

完——

继续。。。

原文地址：https://blog.csdn.net/lrq13965748542/article/details/144829102

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！