[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和

这篇具有很好参考价值的文章主要介绍了[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和

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

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

[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和,LEETCODE,leetcode,算法,数据结构

题目分析

(1) 数组内数字是升序

(2) 目标值为target

(3) 找两数之和为target

解题思路

找两个数字的和与目标值相等,我们可以想到使用双指针解法。

解法:双指针

数组是升序

如果两个指针都在前,当和小于目标值时候,就无法判断移动哪个指针了。所以我们的指针是一前一后:左指针从0开始,右指针从size-1开始。

如果和小于目标值,就让小的数字向右移动。

如果大于目标值,就让大的数字向左移动。

示例:

[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和,LEETCODE,leetcode,算法,数据结构

看到这里,大家先去实现代码,再来看后面的内容。


代码实现
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        vector<int> ret;
        int left = 0, right = price.size()-1;
        while(left != right)
        {
            if(price[left] + price[right] > target) right--;
            else if(price[left] + price[right] < target) left++;
            else
            {
                ret.push_back(price[left]);
                ret.push_back(price[right]);
                break;
            }
        }
        return ret;
    }
};

[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和,LEETCODE,leetcode,算法,数据结构

总结

这道题比较简单。

三数之和

15. 三数之和

[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和,LEETCODE,leetcode,算法,数据结构

题目分析

(1) 找三数之和为0

(2) 三数不可以重复

解题思路

这和之前的两数之和十分相似,我们可以把它转变成两数之和来做。(首先理解上一道题)

解法:双指针

我们可以先排序,再让target = 0 - k(k为三数中的任意一个),这样就变成了求两数之和了(left从k后面的位置,right为size-1)。

即为:排序后,我们固定一个数为k,从它后面的数中找出两个数和为0-k即可。

最后我们必须保证不能有重复的数返回:

排序后,相同的数都会相邻,在找出一组数后,我们将左右指针分别进行迭代,去重。

当然固定的k也需要去重,和上面的方法一样。

示例:nums[] = {-4, -4, -4, 0, 0, 0, 1, 3, 4, 4, 4}

[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和,LEETCODE,leetcode,算法,数据结构

看到这里,先去尝试实现代码,再来看下面的内容吧。


代码实现
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); )
        {
            if(nums[i] > 0) break;
            int left = i+1, right = nums.size()-1;
            int target = 0 - nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > target) right--;
                else if(sum < target) left++;
                else
                {
                    ret.push_back({nums[i], nums[left], nums[right]});//C++11
                    left++, right--;
                    while(left < right && nums[left-1] == nums[left]) left++;
                    while(left < right && nums[right+1] == nums[right]) right--;
                }
            }
            i++;
            while(i < nums.size() && nums[i] == nums[i-1]) i++;
        }
        return ret;
    }
};

[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和,LEETCODE,leetcode,算法,数据结构

总结

细节1:题目让我们去三数和为0,我们把0-k当作目标值,转换为两数之和。

细节2:去重,先对指针进行移动,再进行判断;“三个指针”都需要进行去重;前提是保证指针不越界。

细节3:left指针从k之后开始

细节4:如果nums[k]到了大于0的位置,我们可以提前结束循环,因为没有两个正数和是负数。(例如nums[k] = 1, target = 0 -1 = -1;由于我们先进行过排序,后面的都是正数。)文章来源地址https://www.toymoban.com/news/detail-744012.html

到了这里,关于[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • lc1074.元素和为目标值的子矩阵数量

    创建二维前缀和数组 两个for循环,外循环表示子矩阵的左上角(x1,y1),内循环表示子矩阵的右下角(x2,y2) 两个for循环遍历,计算子矩阵的元素总和 四个变量,暴力破解的时间复杂度为 O(m^2*n^2) (m、n为matrix数组的行数和列数) 优化 计算每一行的前缀和,而不是整个矩阵

    2024年02月14日
    浏览(37)
  • 【VUE】数字动态变化到目标值-vue-count-to

    vue-count-to是一个Vue组件,用于实现数字动画效果。它可以用于显示从一个数字到另一个数字的过渡动画。  插件名:vue-count-to 官方仓库地址:GitHub - PanJiaChen/vue-countTo: It\\\'s a vue component that will count to a target number at a specified duration https://panjiachen.github.io/countTo/demo/ 官方Demo地址:

    2024年02月11日
    浏览(41)
  • 【二分查找】【双指针】LeetCode:2565最少得分子序列

    【动态规划】【广度优先】LeetCode2258:逃离火灾 二分查找算法合集 有序向量的 二分查找 ,初始化完成后,向量不会修改。 双指针 : 用于计算子字符串是s的字符串的子系列。 给你两个字符串 s 和 t 。 你可以从字符串 t 中删除任意数目的字符。 如果没有从字符串 t 中删除字

    2024年02月05日
    浏览(57)
  • 【Leetcode】179. 最大数

    给定一组非负整数 nums ,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。 注意 :输出结果可能非常大,所以你需要返回一个字符串而不是整数。 示例1: 示例2: 提示: 1 = nums.length = 100 0 = nums[i] = 10 9

    2024年02月07日
    浏览(35)
  • LeetCode LCR 026. 重排链表

    LCR 026. 重排链表 中等 128 相关企业 给定一个单链表 L 的头节点 head ,单链表 L 表示为: L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1: 输入: head = [1,2,3,4] 输

    2024年02月09日
    浏览(39)
  • ⭐北邮复试刷题LCR 018. 验证回文串__双指针 (力扣119经典题变种挑战)

    给定一个字符串 s ,验证 s 是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写。 本题中,将空字符串定义为有效的 回文串 。 示例 1: 输入: s = “A man, a plan, a canal: Panama” 输出: true 解释:“amanaplanacanalpanama” 是回文串 示例 2: 输入: s = “race a car” 输出: false

    2024年02月22日
    浏览(35)
  • LeetCode - LCR 008.长度最小的子数组

    LeetCode - 209. 长度最小的子数组 由于此问题分析的对象是「⼀段连续的区间」,因此可以考虑 「滑动窗口」 的思想来解决这道题。 让滑动窗口满足:从 i 位置开始,窗口内所有元素的和小于target (那么当窗口内元素之和 第⼀次大于等于目标值的时候,就是i 位置开始,满足

    2024年04月27日
    浏览(30)
  • 【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年01月20日
    浏览(43)
  • 每日一题:LeetCode-LCR 007. 三数之和

    前言: 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈    🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉 算法 👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长

    2024年02月01日
    浏览(49)
  • 每日一题:LeetCode-LCR 143.子结构判断

    前言: 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈    🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉 算法 👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长

    2024年02月05日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包