算法基础学习Day4(双指针)

在这里插入图片描述

文章目录

  • 1.题目
    • 2.题目解答
    • 1.查找总价格为目标值的两个商品
      • 1.1题目及题目解析
      • 1.2算法学习
        • 暴力解法
        • 优化算法
      • 1.3代码提交
    • 2.三数之和
      • 2.1题目及题目解析
      • 2.2算法学习
      • 2.3代码提交

1.题目

  1. LCR 179. 查找总价格为目标值的两个商品 - 力扣(LeetCode)
  2. 15. 三数之和 - 力扣(LeetCode)

2.题目解答

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

1.1题目及题目解析

image-20241208160745414

1.2算法学习

暴力解法

这里我们还是先进行暴力解法,根据暴力解法去寻找更好的算法:

直接进行枚举比对即可:

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        vector<int> end;
        for(int i =0 ;i<=price.size()-2;i++)
        {
            for(int j =i+1;j<=price.size()-1;j++)
            {
                if(price[i]+price[j]==target)
                {
                    end.push_back(price[i]);
                    end.push_back(price[j]);
                }
            }
        }
        end.resize(2);
        return end;
    }
};

当然这里是过不了的

image-20241208160806228

优化算法

这里因为数组是有序的我们仍然要用指针的方法

先让left指针指向最左边,让right指针指向最右边

直接让leftright指向的数进行相加和target进行比较

会出现以下两种情况:

  1. leftright指向的数比target

    因为数组有序,当left不行时,去找比left大的数,直接让left++

image-20241208163446069

  1. leftright指向的数比target

    此时就不能去移动left了,应该让right向左移动了所以应该是right--

image-20241208163755978

  1. 将这两部分写成代码如下:

    while(left<right)
    {
        if(price[left]+price[right]>target)
        {
            right--;
        }
        else if(price[left]+price[right]<target)
        {
            left++;
        }
        else
        {
            end.push_back(price[left]);
            end.push_back(price[right]);
            break;
        }
    }
    

1.3代码提交

全部代码如下:

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        vector<int> end;
        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
            {
                end.push_back(price[left]);
                end.push_back(price[right]);
                break;
            }
        }
        return end;
    }
};

2.三数之和

2.1题目及题目解析

image-20241208165256882

2.2算法学习

这里有两种解法:

  1. 解法一:排序+暴力枚举+利用set去重
  2. 解法二:排序+双指针

这里我们主要演示第二章解法,并且不用set去重:

首先先选择一个固定数,此时就会发现一个数学关系:

当剩下的两个数为固定数的相反数时,就会成立

所以后面就变成了和前一题一样的解法:找两个数的和

如图:

image-20241208171358318

但是这里仍然有个问题:

如何去重?

这里有两种解决方法:

  1. 直接用容器去解决(这里我们就不在使用了)
  2. 找到第一个结果,可以让left和right跳过重复元素,同时固定的数字也要跳过重复元素,但是这里在用循环+/-时一定要注意不要越界访问

2.3代码提交

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> vv;
        vector<int> v;
        sort(nums.begin(), nums.end());
        int i = 0;
        while (i < nums.size()) {
            if(nums[i]>0)
            {
                break;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right) 
            {
                if (nums[left] + nums[right] > (-nums[i])) 
                {
                    right--;
                } 
                else if (nums[left] + nums[right] < (-nums[i])) 
                {
                    left++;
                } 
                else 
                {
                    v.push_back(nums[i]);
                    v.push_back(nums[left]);
                    v.push_back(nums[right]);
                    vv.push_back(v);
                    v.clear();
                   left++,right--;//这里先进行++/--
                    while (left<right && nums[left] == nums[left - 1]) //这里比较就要-1
                    {
                        left++;
                    }
                    while (right>left && nums[right] == nums[right + 1]) 
                    {
                        right--;
                    }
                }
            }
            i++;
            while ( i < nums.size()&&nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return vv;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/932215.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

哪里可以找到高质量的街道夜景短视频素材?夜景素材网站推荐

在短视频创作的浪潮中&#xff0c;街道夜景作为一种视觉效果独特、氛围浓郁的题材&#xff0c;深受创作者的青睐。不论是商业广告、创意短片还是个人Vlog&#xff0c;街道夜景的视频素材都能为你的作品增添不小的分量。那么&#xff0c;在哪里可以找到这些高质量的街道夜景短视…

实习冲刺第四十三天

25.K个一组翻转链表 给你链表的头节点 head &#xff0c;每 k 个节点一组进行翻转&#xff0c;请你返回修改后的链表。 k 是一个正整数&#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍&#xff0c;那么请将最后剩余的节点保持原有顺序。 你不能只是单…

[计算机网络] HTTP/HTTPS

一. HTTP/HTTPS简介 1.1 HTTP HTTP&#xff08;超文本传输协议&#xff0c;Hypertext Transfer Protocol&#xff09;是一种用于从网络传输超文本到本地浏览器的传输协议。它定义了客户端与服务器之间请求和响应的格式。HTTP 工作在 TCP/IP 模型之上&#xff0c;通常使用端口 …

微信创建小程序码 - 数量不受限制

获取小程序码&#xff1a;小程序码为圆图&#xff0c;且不受数量限制。 目录 文档 接口地址 请求方式 功能描述 注意事项 获取 scene 值 请求参数 返回参数 对接 请求方法 获取小程序码 调用获取小程序码 总结 文档 接口地址 https://api.weixin.qq.com/wxa/get…

在做题中学习(79):最小K个数

解法&#xff1a;快速选择算法 说明&#xff1a;堆排序也是经典解决问题的算法&#xff0c;但时间复杂度为&#xff1a;O(NlogK)&#xff0c;K为k个元素 而将要介绍的快速选择算法的时间复杂度为: O(N) 先看我的前两篇文章&#xff0c;分别学习&#xff1a;数组分三块&#…

第427场周赛: 转换数组、用点构造面积最大的矩形 Ⅰ、长度可被 K 整除的子数组的最大元素和、用点构造面积最大的矩形 Ⅱ

Q1、转换数组 1、题目描述 给你一个整数数组 nums&#xff0c;它表示一个循环数组。请你遵循以下规则创建一个大小 相同 的新数组 result &#xff1a; 对于每个下标 i&#xff08;其中 0 < i < nums.length&#xff09;&#xff0c;独立执行以下操作&#xff1a; 如…

【中间件开发】Redis基础命令详解及概念介绍

文章目录 前言一、Redis相关命令详解及原理1.1 string、set、zset、list、hash1.1.1 string1.1.2 list1.1.3 hash1.1.4 set1.1.5 zset 1.2 分布式锁的实现1.3 lua脚本解决ACID原子性1.4 Redis事务的ACID性质分析 二、Redis协议与异步方式2.1 Redis协议解析2.1.1 redis pipeline…

运输层4——TCP格式(重点!)

目录 一、TCP报文段格式 二、最大报文长度 MSS 一、TCP报文段格式 长度&#xff1a;前20个字节固定 后4n个字节&#xff08;报文段格式不固定&#xff09; 1、源端和目的端&#xff1a;各2个字节 作用&#xff1a;指明TCP链接的发送 2、序号 4字节 作用&#xff1…

「Mac玩转仓颉内测版46」小学奥数篇9 - 基础概率计算

本篇将通过 Python 和 Cangjie 双语实现基础概率的计算&#xff0c;帮助学生学习如何解决简单的概率问题&#xff0c;并培养逻辑推理和编程思维。 关键词 小学奥数Python Cangjie概率计算 一、题目描述 假设有一个袋子中有 5 个红球和 3 个蓝球&#xff0c;每次从袋子中随机…

从变更到通知:使用Python和MongoDB Change Streams实现即时事件监听

MongoDB提供了一种强大的功能&#xff0c;称为Change Streams&#xff0c;它允许应用程序监听数据库中的变更事件&#xff0c;并在数据发生变化时立即做出响应。这在mysql数据库是不具备没有这个功能的。又如&#xff1a;我们在支付环节想一直监听支付回调的状态&#xff0c;就…

决策树:ID3、C4.5和CART特征选择方式

1 前言 该文章主要目的是记录ID3、C4.5和CART特征选择方式&#xff0c;这里只对决策树进行简单介绍。 决策树&#xff08;Decision Tree&#xff09;算法是一种有监督学习算法&#xff0c;它利用分类的思想&#xff0c;根据数据的特征构建数学模型&#xff0c;从而达到数据的筛…

2023 年“泰迪杯”数据分析技能赛B 题企业财务数据分析与造假识别

2023 年“泰迪杯”数据分析技能赛B 题企业财务数据分析与造假识别 一、背景 财务数据是指企业经营活动和财务结果的数据记录&#xff0c;反映了企业的财务状况 与经营成果。对行业、企业的财务数据进行分析&#xff0c;就是要评价其过去的经营业绩、 衡量现在的财务状况、预测…

UE5.5 Geometry库平面切割原理分析

平面切割--FMeshPlaneCut 平面定义: 面上一个点 法线 算法流程如下 求几何体所有顶点和面的有向距离(Signs) Sign计算&#xff1a; float Sign (VertexPos - PlaneOrigin).Dot(PlaneNormal); 遍历所有几何体所有交叉边, 进行SplitEdge 对于位于切割面两侧的交叉边(Sign…

【计算机学习笔记】GB2312、GBK、Unicode等字符编码的理解

之前编写win32程序时没怎么关注过宽字符到底是个啥东西&#xff0c;最近在编写网络框架又遇到字符相关的问题&#xff0c;所以写一篇文章记录一下&#xff08;有些部分属于个人理解&#xff0c;如果有错误欢迎指出&#xff09; 目录 几个常见的编码方式Unicode和UTF-8、UTF-16、…

CSS 快速上手

目录 一. CSS概念 二. CSS语法 1. 基本语法规范 2. CSS的三种引入方式 (1) 行内样式 (2) 内部样式表 (3) 外部样式表 3. CSS选择器 (1) 标签选择器 (2) 类选择器 (3) id选择器 (4) 通配符选择器 (5) 复合选择器 <1> 空格 <2> 没有空格 <3> &q…

【时间之外】IT人求职和创业应知【60】-卡脖子

目录 新闻一&#xff1a;达成合作&#xff0c;将在中国推出生成式人工智能服务 新闻二&#xff1a;机器人新赛道 新闻三&#xff1a;简化用户信息获取流程&#xff0c;提升小程序体验 去年人口出生下降&#xff0c;3年以后&#xff0c;幼儿园要关闭很多&#xff0c;6年以后小…

centos9升级OpenSSH

需求 Centos9系统升级OpenSSH和OpenSSL OpenSSH升级为openssh-9.8p1 OpenSSL默认为OpenSSL-3.2.2&#xff08;根据需求进行升级&#xff09; 将源码包编译为rpm包 查看OpenSSH和OpenSSL版本 ssh -V下载源码包并上传到服务器 openssh最新版本下载地址 wget https://cdn.openb…

node.js中实现GETPOST请求

创建基本的服务器 const express require(express); const indexRouter require(./router); // 引入路由 const app express(); const port 3000; // 挂载路由 app.use(/api, indexRouter); app.listen(port, () > {console.log(Server is running on http://localhost…

shell 条件测试

一、命令执行结果判定 && &#xff1a; 在命令执行后如果没有任何报错时会执行符号后面的动作 || &#xff1a; 在命令执行后有报错执行符号后的动作 [rootlong ~]# a10 [rootlong ~]# echo $a 10 [rootlong ~]# [ $a -gt "5" ] && echo yes || e…

JS中的原型链与继承

原型链的类比 JS中原型链&#xff0c;本质上就是对象之间的关系&#xff0c;通过protoype和[[Prototype]]属性建立起来的连接。这种链条是动态的&#xff0c;可以随时变更。 这个就跟C/C中通过指针建立的关系很相似&#xff0c;比如&#xff0c;通过指针建立一个链表&#xf…