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

双指针

  • 1.有效三角形的个数
  • 2.和为S的两个数字
  • 3. 三数之和
  • 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. 三数之和

题目链接: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.rhkb.cn/news/316558.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

react实现时钟翻牌效果

需求&#xff1a;随着数字的变动要求有时钟翻动动效 问题&#xff1a;只在加载时有动效 解决方案&#xff1a;通过判断数字改变&#xff08;这里通过新旧数值变动来判断&#xff0c;不贴代码啦&#xff09;&#xff0c;每次变动的时候手动把animationIterationCount设置为inf…

Android --- 网络请求

通常在 Android 中进行网络连接一般使用 Scoket 和HTTP&#xff0c;HTTP 请求方式比 Scoket 多。HTTP 请求一般采用原生的 HttpClient 和 HttpUrlConnection 的两种网络访问方式&#xff08;系统自带的&#xff09;。但是在 Android 5.0 的时候 Google 就不推荐使用 HttpClient…

Python自学篇3-PyCharm开发工具下载、安装及应用

一、Python开发工具 自学篇1中讲到了安装Python之后出现的几个应用程序&#xff0c;其中IDLE、Python.exe都可以用来编写python程序&#xff0c;也可以进行调试&#xff1b;但是比较基础&#xff0c;比较原始&#xff0c;调试不方便&#xff0c;界面也不友好&#xff0c;需要更…

笔记本电脑耗电和发热比较厉害怎么处理

工作中会遇到有同事反馈笔记本电脑耗电和发热比较厉害&#xff0c;主要检查以下几个地方 1、CPU频率 很多人觉得是cpu使用率高就代表电脑跑得快&#xff0c;发热量就大&#xff0c;其实不是的&#xff0c;主要是看的cpu频率&#xff0c;频率越高&#xff0c;电脑发热量越大。如…

Visual Studio中怎样更改Nuget程序包源

场景 Visual Studio 2019 在使用NuGet添加依赖包时&#xff0c;在预览中搜索不到程序包。 排查下NuGet的程序包源为本地。 将程序包源修改下。 实现 在解决方案上右击选择管理解决方案中的NuGet程序包(在 Visual Studio 中打开“工具”>“选项”>“NuGet 包管理器”…

idea上传项目到gitee(码云)

1、打开码云&#xff0c;新建仓库 2、创建 3、这就是创建成功的页面 4、复制仓库地址&#xff0c;后面需要用到 2、打开我们的项目&#xff1a;例如我现在的项目 1、idea创建git仓库 2、选择我们项目文件夹的目录 3、查看文件是否变色&#xff0c;变色表示成功了 4、添加到缓…

STM32的GPIO输入和输出函数详解

系列文章目录 STM32单片机系列专栏 C语言术语和结构总结专栏 文章目录 1. GPIO模式 2. GPIO输出 2.1 RCC 2.2 GPIO 3. 代码示例 3.1 RCC时钟 3.2 GPIO初始化 3.3 GPIO输出函数 3.4 推挽输出和开漏输出 4. GPIO输入 4.1 输入模式 4.2 数据读取函数 5. C语言语法 1…

为什么很多企业都使用OV SSL证书

我们要了解什么是SSL OV证书 SSL OV证书&#xff0c;即组织验证型SSL证书&#xff0c;它要求证书颁发机构对申请证书的组织进行身份验证&#xff0c;确认组织的真实性后&#xff0c;才会发放证书。这种验证方式提高了安全性&#xff0c;因为它确保了证书背后的实体是真实存在的…

C语言(操作符)1

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸各位能阅读我的文章&#xff0c;诚请评论指点&#xff0c;关注收藏&#xff0c;欢迎欢迎~~ &#x1f4a5;个人主页&#xff1a;小羊在奋斗 &#x1f4a5;所属专栏&#xff1a;C语言 本系列文章为个人学习笔记&#x…

基于Springboot的点餐平台

基于SpringbootVue的点餐平台的设计与实现 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringbootMybatis工具&#xff1a;IDEA、Maven、Navicat 系统展示 用户登录 首页展示 菜品信息 菜品资讯 购物车 后台登录 用户管理 菜品分类管理 菜品信息管理 …

【Linux】dlopen: /lib/x86_64-linux-gnu/libm.so.6: version `GLIBC_2.29‘ not found

[30116] Error loading Python lib /tmp/_MEIlvdUu6/libpython3.8.so.1.0: dlopen: /lib/x86_64-linux-gnu/libm.so.6: version GLIBC_2.29 not found (required by /tmp/_MEIlvdUu6/libpython3.8.so.1.0)1 cd到指定路径 cd /usr/local 2 下载 wget http://ftp.gnu.org/gnu/gl…

NXP i.MX8系列平台开发讲解 - 3.10 Linux PCIe资源分配与访问(二)

专栏文章目录传送门&#xff1a;返回专栏目录 目录 1. PCIe BFD 2. PCIe 配置空间 2.1 PCIe 配置空间访问 PCIe I/O访问方法 PCIe MMIO访问方法 3. PCIe BAR相关 4. PCIe Capbility 5. PCIe 操作 本文将重点讲解PCIe的资源访问相关内容&#xff0c;对于PCIe资源访问是从…

设计不外流,保护创意的同时锁住图纸安全!

在设计行业中&#xff0c;图纸和创意文稿的安全至关重要&#xff0c;因为它们体现了企业的创新能力和核心竞争力。华企盾DSC数据防泄密系统提供了一系列功能&#xff0c;可以有效地保护这些珍贵的设计和文档不被外泄。以下是如何利用华企盾DSC系统保障设计图纸安全的关键措施&a…

【工具】-根源上解决VScode打印输出乱码的问题

目录 1 第一步&#xff1a; 改编译命令&#xff0c;保持一致2 第二步&#xff1a; 更改VScode的编码格式-保持一致 1 第一步&#xff1a; 改编译命令&#xff0c;保持一致 看一下你的控制台的编译的命名后缀&#xff0c;有两个关键的参数&#xff0c;如下图&#xff1a; “-f…

LT9611UXC双端口 MIPI DSI/CSI 转 HDMI2.0,带音频

1. 说明 LT9611UXC 是一款高性能 MIPI DSI/CSI 至 HDMI2.0 转换器。MIPI DSI/CSI 输入具有可配置的单端口或双端口&#xff0c;具有 1 个高速时钟通道和 1~4 个高速数据通道&#xff0c;工作速率最高为 2Gbps/通道&#xff0c;可支持高达 16Gbps 的总带宽。 LT9611UXC 支持突发…

双目深度估计原理立体视觉

双目深度估计原理&立体视觉 0. 写在前面1. 双目估计的大致步骤2. 理想双目系统的深度估计公式推导3. 双目标定公式推导4. 极线校正理论推导 0. 写在前面 双目深度估计是通过两个相机的对同一个点的视差来得到给该点的深度。 标准系统的双目深度估计的公式推导需要满足:1)两…

【算法每日一练】

蛮有意思的的一道题&#xff0c;最后要判断能否成为一种1~n的全排列&#xff0c;我最这样做的&#xff1a; 整个数组先排序一下。假设遍历到了i&#xff0c;那就判断前面b和r的个数&#xff0c;但是有想到了后面可能还会对前面的结果产生影响&#xff0c;所以就抛弃了这个想法…

二、再识VUE-MVVM

一、初识VUE 二、再识VUE-MVVM 三、VUE数据代理 MVVM Vue.js 专注于 MVVM 模型的 ViewModel 层。它通过双向数据绑定把 View 层和 Model 层连接了起来。实际的 DOM 封装和输出格式都被抽象为了 Directives 和 Filters。 ViewModel 一个同步 Model 和 View 的对象。在 Vue.js…

Stable Diffusion基础:ControlNet之线稿成图

今天继续给大家分享Stable Diffusiion的基础能力&#xff1a;ControlNet之线稿成图。 所谓线稿就是由一条条的线段组成的图形&#xff0c;主要用于绘画和设计领域的打底稿、表达构想和预见最终效果。 所谓线稿成图就是利用 Stable Diffusion ControlNet 的能力&#xff0c;依…

极目楚天 共襄星汉 | 同元软控受邀参加2024年中国航天大会

4月23日至26日&#xff0c;2024 年中国航天大会&#xff08;CSC2024&#xff09;在湖北省武汉市成功举办。大会由中国宇航学会和中国航天基金会联合主办&#xff0c;以“极目楚天 共襄星汉”为主题&#xff0c;汇聚国内外航天领域知名专家、学者、管理者&#xff0c;深入探讨航…