【基础算法总结】双指针算法二

news/2024/5/20 16:05:08

双指针

  • 1.有效三角形的个数
  • 2.和为S的两个数字
  • 3.和为S的两个数字
  • 4.四数之和

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

1.有效三角形的个数

题目链接:633.有效三角形的个数

题目描述

在这里插入图片描述
一般三角形我们判断方法是任意两边之和大于第三边
在这里插入图片描述
算法原理:

解法一: 暴力求解

选三个数进行判断,一般我们一定会想到三层for循环进行判断,下面是伪代码,时间复杂度O(N^3)
在这里插入图片描述
解法二:利用单调性,使用双指针算法来解决问题

任意两边之和大于第三边,三个数需要判断三次
a+b>c
a+c>b
b+c>a

现在a、b、c三个数,先对它们进行排序,a<=b<=c;
a+b>c
a+c>b
b+c>a
我们只需要判断一次 a+b>c就也把下面两次判断包括了。因为c是最大的!

在这里插入图片描述
注意这只是固定了10一次循环,还要在从后往前固定

  1. 固定最大的数
  2. 在最大数的左区间内,使用双指针算法,快速统计符合要求的三元组个数
class Solution {
public:int triangleNumber(vector<int>& nums) {  //1.优化sort(nums.begin(),nums.end());//2.利用双指针快速解决问题int sum=0;for(int i=nums.size()-1;i>=2;--i)//先固定最大数{//利用双指针快速统计符合要求的三元组个数int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){sum+=(right-left);--right;}else{++left;}}}return sum;}
};

总结:有些题可以进行排序或者已经排好了序,然后利用单调性,使用双指针算法解决问题,双指针一个指向最小值,一个指向最大值,然后根据题意利用单调性一次排除一批。

2.和为S的两个数字

题目链接:JZ57 和为S的两个数字

题目描述
在这里插入图片描述

算法原理

解法一:暴力枚举求解O(N^2)
拿到题我们马上就会想到暴力求解,两层for循环,以下是伪代码
在这里插入图片描述

解法2:使用单调性,使用双指针算法解决问题
本题排好序了,我们直接使用双指针即可,一个指向最左边,一个指向最右边。然后根据条件利用单调性一次排除一批。O(N)

在这里插入图片描述

class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array,int sum) {int left=0,right=array.size()-1,ret=0;while(left<right){ret=array[left]+array[right];if(ret>sum) --right;else if(ret<sum) ++left;else return {array[left],array[right]};}return {};}
};

3.和为S的两个数字

题目链接:15. 三数之和

题目描述
在这里插入图片描述
题目分析

这道题我们根据它的用例来分析,要找下标不同的数,使其相加和为0。下面虽然有三组解,下标也不同,但是第一组和第三组它们的数是相同的,因此只能去重留下一组。
在这里插入图片描述

算法原理:

一般这里我们还是首先会想到暴力求解,这是没问题的,因为我们的优化就是从暴力求解上来的。

对于这道题,它要最后把结果还要去重,我们一般考虑得到结果然后每个排序之后在去重。其实我们可以先排序。然后在去重,去重我们有容器set和unordered_set,因此第一种解法出来了。

解法一:排序+暴力枚举+利用set去重

解法二:排序之后,使用单调性,使用双指针算法解决问题

本题是找三元组,因此我们排好序之后,固定一个数,然后利用双指针求解。所以以后遇到三元组的问题可以采用这种方法

  1. 排序
  2. 固定一个数a
  3. 在该数后面的区间内,利用 “双指针算法” 快速找到两个的和等于-a即可

在这里插入图片描述

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//1.排序sort(nums.begin(),nums.end());vector<vector<int>> vc;//2.利用双指针解决问题for(int i=0;i<nums.size()-2;++i)//固定a{if(nums[i]>0)//小优化break;int left=i+1,right=nums.size()-1,target=-nums[i];while(left<right){int sum=nums[left]+nums[right];if(sum>target) --right;else if(sum<target) ++left;else{vc.push_back({nums[i],nums[left],nums[right]});//不漏++left,--right;//去重left,rightwhile(left < right && nums[left] == nums[left-1]) ++left;while(left < right && nums[right] == nums[right+1]) --right;}}//去重iwhile(i < nums.size()-2 && nums[i] == nums[i+1]) ++i;}return vc;        }
};

4.四数之和

题目链接:18.四数之和

题目描述
在这里插入图片描述
这道题和上面三数之和几乎一模一样

算法原理:

解法一:排序+暴力枚举+容器set去重
时间复杂度O(N^4)

解法二:排序+双指针

  1. 依次固定一个数 a
  2. 在 a 后面的区间内,利用 “三数之和” 找到三个数,是这三个数字的和等于 target - a 即可

三数之和

  1. 依次固定一个数 b
  2. 在 b 后面的区间内,利用 “双指针” 找到两个数,使这两个数的和等于 target - a - b 即可

处理细节问题:

  1. 去重
  2. 不漏
    在这里插入图片描述
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {//1.排序sort(nums.begin(),nums.end());//2.利用双指针解决问题vector<vector<int>> ret;int n=nums.size();for(int i=0;i<n-3;++i)//固定数 a{//利用 三数之和for(int j=i+1;j<n-2;++j) //固定数 b{//双指针int left=j+1,right=n-1;int aim=target-nums[i]-nums[j];while(left<right){int sum=nums[left]+nums[right];if(sum>aim) --right;else if(sum<aim) ++left;else{ret.push_back({nums[i],nums[j],nums[left],nums[right]});//不漏++left;--right;//去重1while(left<right && nums[left] == nums[left-1]) ++left;while(left<right && nums[right] == nums[right+1]) --right;}}//去重2while(j+1 < n-2 && nums[j+1] == nums[j]) ++j;}//去重3while(i+1 < n-3 && nums[i+1] == nums[i]) ++i;}return ret;}
};

注意这里会有数据溢出的问题。

在这里插入图片描述

因此两数相减的时候,使用long long

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {//1.排序sort(nums.begin(),nums.end());//2.利用双指针解决问题vector<vector<int>> ret;int n=nums.size();for(int i=0;i<n-3;++i)//固定数 a{//利用 三数之和for(int j=i+1;j<n-2;++j) //固定数 b{//双指针int left=j+1,right=n-1;long long aim=(long long)target-nums[i]-nums[j];while(left<right){int sum=nums[left]+nums[right];if(sum>aim) --right;else if(sum<aim) ++left;else{ret.push_back({nums[i],nums[j],nums[left],nums[right]});//不漏++left;--right;//去重1while(left<right && nums[left] == nums[left-1]) ++left;while(left<right && nums[right] == nums[right+1]) --right;}}//去重2while(j+1 < n-2 && nums[j+1] == nums[j]) ++j;}//去重3while(i+1 < n-3 && nums[i+1] == nums[i]) ++i;}return ret;}
};

http://www.mrgr.cn/p/31814868

相关文章

前端工程化Vue使用Node.js设置国内高速npm镜像源(踩坑记录版)

前端工程化Vue使用Node.js设置国内高速npm镜像源&#xff08;踩坑记录版&#xff09; 此篇仅为踩坑记录&#xff0c;并未成功更换高速镜像源&#xff0c;实际解决方法见文末跳转链接。 1.自身源镜像 自身镜像源创建Vue项目下载速度感人 2.更改镜像源 2.1 通过命令行配置 前提…

京东web端h5st—4.7逆向分析

声明 本文章中所有内容仅供学习交流,抓包内容、敏感网址、数据接口均已做脱敏处理,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关,若有侵权,请联系我立即删除! 目标网站 aHR0cHM6Ly93d3cuamQuY29tLw== 分析流程了解h5st 看了sha256相关加密算法逻辑b…

API和微服务设计的优化方式有哪些?

在构建响应迅速、用户体验良好的应用程序中&#xff0c;API性能的优化至关重要。在构建高性能的API时&#xff0c;采取综合策略是至关重要的。通过采用一系列策略&#xff0c;我们可以确保API在处理请求时高效运行&#xff0c;提供流畅的服务。 一、API和微服务设计的优化可以…

XYCTF2024-web-wp

怎么全是傻逼绕过题。 不想评价,就随便打着玩,除了最后一道java反序列化搞心态,其他的ak了:简单题不想说,http注意一下代理是用Via就行,warmup直接:http://xyctf.top:37034/?val1=240610708&val2=QNKCDZO&md5=0e215962017&XYCTF=240610708&XY=24061070…

深入mysql索引

1. 索引 索引是对数据库表中一列或多列的值进行排序的一种结构。 MySQL索引的建立对于MySQL的高效运行是很重要的,索引可以大大提高MySQL的检索速度。索引只是提高效率的一个因素,如果你的MySQL有大数据量的表,就需要花时间研究建立最优秀的索引,或优化查询语句。 简单类比…

平衡树炫酷科技

炫酷平衡树科技标题是吸引你点进来的 Case 1 LCT 的 access 操作应该可以实现某种区间覆盖的操作(听同学讲的,具体的还待讨论) Case 2 众所周知,可并堆中左偏树合并是这样写的(记 \(dist\) 为 \(rd\)): merge(A, B)if !A: return Bif !B: return Aif B.val > A.valsw…

杰发科技AC7840——ADC简介(1)_双路ADC同时使用

0. 简介 1. 特性 2. 双路ADC Sample里面没有双路的&#xff0c;以为那个规则组只有一个通道&#xff0c;看了外设寄存器才发现&#xff0c;原来他的通道是双路的。 注意1: ADC硬件引脚的配置 注意2: 规则组长度设置和 RSEQ序列号和CH通道号组合应该就对应了转换顺序&#xff0…

UniAD:以规划为导向的端到端自动驾驶

文章链接 这个文章是CVPR2023 Best Paper https://arxiv.org/pdf/2212.10156 提出背景 以往的自动驾驶多数是为不同的任务场景设计部署单独的模型&#xff0c;这样子组成的系统会很复杂如图a。 图b这是多任务共享一个主干&#xff0c;但还是要分离训练&#xff0c;而且不是…

ChatGPT有记忆了?!持久记忆(Memory)功能详细解读和教程!

大家好&#xff0c;我是木易&#xff0c;一个持续关注AI领域的互联网技术产品经理&#xff0c;国内Top2本科&#xff0c;美国Top10 CS研究生&#xff0c;MBA。我坚信AI是普通人变强的“外挂”&#xff0c;所以创建了“AI信息Gap”这个公众号&#xff0c;专注于分享AI全维度知识…

如何使得 单个项目有与其他项目 不一样的对齐方式

今天修改项目的样式&#xff0c;有这么个问题&#xff0c;便记录下。 align-self属性允许单个项目有与其他项目不一样的对齐方式&#xff0c;可覆盖align-items属性。默认值为auto&#xff0c;表示继承父元素的align-items属性&#xff0c;如果没有父元素&#xff0c;则等同于…

如何解决升级IntelliJ IDEA 2024后 打开项目就自动闪退关闭问题的终极指南

title: “&#x1f42f; 解决升级IntelliJ IDEA 2024后项目自动关闭的终极指南” date: 2024-04-23 author: 猫头虎 profile: CSDN 文章目录 title: "&#x1f42f; 解决升级IntelliJ IDEA 2024后项目自动关闭的终极指南" date: 2024-04-23 author: 猫头虎 profile: …

萌面匣超萌的小金刚

一款非常精致的金属机箱来了这款机箱支持的主板:畅网微控 P5 N100、N200、N305 V3版本的开发版 特点:卖家定制了背板+定制万兆网卡的转接板说说优点:贵 这款6盘的机箱是2.5英寸的小硬盘机箱 散热不错,也不怕化了 戴尔的硬盘架很专业 支持万兆 带wifi的小机器 适合长期使用,…

Games 101: 旋转矩阵

旋转矩阵 本文主要介绍了旋转矩阵的推导,分为两种方式:旋转坐标 旋转坐标轴 以下坐标系都是右手坐标系旋转坐标 已知坐标点\(A(x_a,y_a)\), 旋转\(\theta\)角后变为坐标点\(B(x_b,y_b)\),求解旋转矩阵.\[{\large \begin{align*} \begin{split} x_a &=r_a \cdot cos(\alp…

ROS学习-启动服务端错误debug

ros2 run examples_rclpy_minimal_service service 输入这个命令用于运行服务节点,这个服务的功能是将两个数字相加,给定a,b两个数,返回sum也就是ab之和。 报错: 2024-04-27 13:11:39.105 [RTPS_TRANSPORT_SHM Error] Failed init_port fastrtps_port7412:open_and_lock_f…

Echarts多条折线图line显示数值和真实数值不一致

问题图: 折线图数据显示不匹配原因:在line的配置项中加了"stack"这一项配置,stack为‘Total’或‘总量’的情况下,y轴不是真实的value的值,而是value的总量值。既后续折现的数值在前数值的基础上相加. 官网对stack的描述:数据堆叠,同个类目轴上系…

mysql定时执行语句

一、前提 #确保事件调度为开放(ON) SHOW VARIABLES LIKE event_scheduler;二、场景 1、创建test01 表&#xff0c;表中存储1000条数据&#xff1b; 2、创建空表test02&#xff0c;表结构与 test01相同&#xff1b; 3、将test01中的数据以每分钟10条的形式转移到test02中去三、…

Docker深入探索:网络与资源控制、数据管理与容器互联以及镜像生成

目录 一、 Docker网络 &#xff08;一&#xff09;Docker网络实现原理 &#xff08;二&#xff09;Docker网络模式 1. Bridge网络&#xff08;默认&#xff09; 2. Host网络 3. None网络 4. Container网络 5. 自定义网络 二、资源控制 &#xff08;一&#xff09;cgr…

IDELAY约束测试

前置条件: DDR模式 LR RISE:1.9-2.1 FALL:1.9-2.1 约束情况1: value:0 IBUF-BUFG-IDELAYE2-IDDR value:0 IBUF-IDELAYE2-IDDRmodule rgmii_dphy (input wire sys_rst_n ,input wire sys_ref_200mhz ,//eth input wire i_eth_r…

补充centos7软件包的方式/编译安装源码包软件/企业案例/linux进程管理/企业管理进程系列命令(企业经验)--8820字详谈

cenros7软件包的安装方式 软件包分类安装方式优缺点rpm包软件开发商编译打包&#xff0c;安装简单&#xff0c;快速软件版本可能偏低&#xff0c;安装路径是固定好的源码包自己手动编译安装并且复杂软件爸爸随意选&#xff0c;可以定制安装路径二进制包解压就可以使用不能进行…

搭建单机版伪分布式Hadoop+Scala+spark

搭建单机版伪分布式Hadoop+Scala+spark 修改ip [root@master ~]# nmcli connection add ifname ens32 con-name ens32 autoconnect yes ipv4.method manual ipv4.gateway 192.168.130.2 ipv4.addresses 192.168.130.102/24 ipv4.dns 114.114.114.114 [root@master ~]# nmcli co…