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

双指针

  • 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,right
                    while(left < right && nums[left] == nums[left-1]) ++left;
                    while(left < right && nums[right] == nums[right+1]) --right;
                }
                
            }
            //去重i
            while(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;
                        //去重1
                        while(left<right && nums[left] == nums[left-1]) ++left;
                        while(left<right && nums[right] == nums[right+1]) --right;

                    }
            
                }
                //去重2
                while(j+1 < n-2 && nums[j+1] == nums[j]) ++j;
            }
            //去重3
            while(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;
                        //去重1
                        while(left<right && nums[left] == nums[left-1]) ++left;
                        while(left<right && nums[right] == nums[right+1]) --right;

                    }
            
                }
                //去重2
                while(j+1 < n-2 && nums[j+1] == nums[j]) ++j;
            }
            //去重3
            while(i+1 < n-3 && nums[i+1] == nums[i]) ++i;
        }
        return ret;
    }
};

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

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

相关文章

深度学习运算:CUDA 编程简介

一、说明 如今&#xff0c;当我们谈论深度学习时&#xff0c;通常会将其实现与利用 GPU 来提高性能联系起来。GPU&#xff08;图形处理单元&#xff09;最初设计用于加速图像、2D 和 3D 图形的渲染。然而&#xff0c;由于它们能够执行许多并行操作&#xff0c;因此它们的实用性…

Python游戏工具包pygame

当你涉及游戏开发时&#xff0c;Pygame是一个强大的工具包&#xff0c;它提供了一系列功能丰富的模块和工具&#xff0c;让你可以轻松地创建各种类型的游戏。在本文中&#xff0c;我将介绍Pygame的依赖以及其详细属性&#xff0c;同时提供一些示例代码来说明其用法。 目录 一…

Github 2024-04-27 开源项目日报 Top9

根据Github Trendings的统计,今日(2024-04-27统计)共有9个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目6TypeScript项目2C++项目1JavaScript项目1Open-Sora: 构建自己的视频生成模型 创建周期:17 天开发语言:Python协议类型:Apache Lic…

嵌入式Linux学习——Linux常用命令(上)

Linux命令行介绍 Linux Shell 简介 Shell 的意思是“外壳”&#xff0c;在 Linux 中它是一个程序&#xff0c;比如/bin/sh、/bin/bash 等。它负责接收用户的输入&#xff0c;根据用户的输入找到其他程序并运行。比如我们输入“ ls”并回车时&#xff0c; shell 程序找到“ ls…

TinyML之Hello world----基于Arduino Nano 33 BLE Sense Rev2的呼吸灯

早期版本的Hello World 这应该是一个逼格比较高的呼吸灯了&#xff0c;用ML来实现呼吸灯功能&#xff0c;之前已经有大佬发过类似的文章&#xff1a;https://blog.csdn.net/weixin_45116099/article/details/126310816 当前版本的Hello World 这是一个ML的入门例程&#xff…

黑马程序员C++学习总结【进阶篇】

本阶段主要针对C泛型编程和STL技术做详细讲解&#xff0c;探讨C更深层的使用 黑马程序员C学习总结【基础篇】 黑马程序员C学习总结【核心篇】 黑马程序员C学习总结【进阶篇】 黑马程序员C学习总结【进阶篇】 一、模板1.函数模板&#xff08;1&#xff09;函数模板2种使用方式&a…

重学java 25.面向对象 权限修饰符、final关键字、代码块

别让平淡生活&#xff0c;耗尽你所有的向往 —— 24.4.27 重点概述 01.知道final修饰成员之后特点 02.会使用静态代码块以及知道静态代码块的使用场景 03.会使用匿名内部类 一、权限修饰符 1.概述 在Java中提供了四种访问权限&#xff0c;使用不同的访问权限修饰符修饰时&#…

为什么 Facebook 不使用 Git?

在编程的世界里&#xff0c;Git 就像水一样常见&#xff0c;以至于我们认为它是创建和管理代码更改的唯一可行的工具。 前 Facebook 员工&#xff0c;2024 年 首先&#xff0c;我为什么关心&#xff1f; 我致力于构建 Graphite&#xff0c;它从根本上受到 Facebook 内部工具的…

第十五届蓝桥杯省赛第二场C/C++B组E题【遗迹】题解

解题思路 错解 贪心&#xff1a;每次都移动至当前最近的对应方块上。 反例&#xff1a; s s s abxac t t t abac 贪心结果&#xff08;下标&#xff09; 0 → 1 → 0 → 4 0 \rightarrow 1 \rightarrow 0 \rightarrow 4 0→1→0→4&#xff0c;答案为 5 5 5。 正确结…

【MRI重建】基于径向采样的GRASP重建实现(matlab)

关于 对比增强MRI和弥散MRI成像,对于时间分辨率要求都比较高,为了捕获高时间空间分辨率,这里使用GRASP方法,重建radial径向采样的MR数据。使用的稀疏正则项为 temporal total variation。 相关文章 https://onlinelibrary.wiley.com/doi/10.1002/mrm.24980 https://onl…

前端学习笔记3

列表、表格与表单​ 列表就是信息资源的一种展示形式。它可以使信息结构化和条理化,并以列表的样式显示出来,以便浏览者能更快捷地获得相应的信息。 3.0 代码访问地址 https://gitee.com/qiangge95243611/java118/tree/master/web/day03 3.1 列表 ​ 列表大致可以分为3类…

mac资源库的东西可以删除吗?提升Mac运行速度秘籍 Mac实用软件

很多小伙伴在使用mac电脑处理工作的时候&#xff0c;就会很疑惑&#xff0c;电脑的运行速度怎么越来越慢&#xff0c;就想着通过删除mac资源库的东西&#xff0c;那么mac资源库的东西可以删除吗&#xff1f;删除了会不会造成电脑故障呢&#xff1f; 首先&#xff0c;mac资源库…

沉浸式推理乐趣:体验线上剧本杀小程序的魅力

在这个信息爆炸的时代&#xff0c;人们的娱乐方式也在不断地推陈出新。其中&#xff0c;线上剧本杀小程序以其独特的沉浸式推理乐趣&#xff0c;成为了许多人的新宠。它不仅让我们在闲暇之余享受到了推理的快乐&#xff0c;更让我们在虚拟的世界里感受到了人性的复杂与多彩。 线…

【hackmyvm】 Quick2靶机

渗透流程 渗透开始1.IP地址 获取2.端口扫描3.任意文件读取4.扫描目录5.总结信息6.漏洞扫描7.php_filter_chain_generator.py使用8.提权 渗透开始 1.IP地址 获取 ┌─[✗]─[userparrot]─[~] └──╼ $fping -ag 192.168.9.0/24 2>/dev/null 192.168.9.124 本机 192.1…

base64格式图片直接显示

<img :src"data:image/png;base64,url"/>

阿斯达年代记游戏下载教程 阿斯达年代记下载教程

《阿斯达年代记&#xff1a;三强争霸》作为一款气势恢宏的MMORPG大作&#xff0c;是Netmarble与STUDIO DRAGON强强联合的巅峰创作&#xff0c;定于4月24日迎来全球玩家热切期待的公测。游戏剧情围绕阿斯达大陆的王权争夺战展开&#xff0c;三大派系——阿斯达联邦、亚高联盟及边…

“PowerInfer:消费级GPU上的高效大语言模型推理引擎“

PowerInfer是由上海交通大学IPADS实验室开发的一个高效大语言模型&#xff08;LLM&#xff09;推理引擎&#xff0c;专为个人电脑&#xff08;PC&#xff09;上的消费者级GPU设计。它通过利用LLM推理中的高局部性&#xff0c;实现了快速且资源消耗低的模型推理&#xff0c;这一…

windows如何安装MySQL(详)

MySQL在Windows上的安装和配置 官网&#xff1a;www.mysql.com 下载地址&#xff1a;MySQL :: Download MySQL Community Server (Archived Versions) window系统 安装包&#xff08;Windows (x86, 64-bit), MSI Installer&#xff09; 压缩包&#xff08;Windows (x86, 64…

Java后端利用百度地图全球逆地理编码,获取地址

声明&#xff1a;本人是在实习项目的时候遇到的问题 一.使用Api分为四步骤全球逆地理编码 rgc 反geo检索 | 百度地图API SDK 步骤1,2自行完成 接下来去获取AK 二.申请AK 登录百度账号 点击创建应用&#xff0c;选择自己想用的服务&#xff0c;我只单选了逆地理编码&#xff…

目标检测的mAP、PR指标含义

基本概念 什么是一个任务的度量标准。对于目标检测任务来说&#xff0c;它的首要目标是确定目标的位置并判别出目标类别。这里已医学图像为例&#xff0c;我们需要计算出血液红细胞&#xff08;RBC&#xff09;、白细胞&#xff08;WBC&#xff09;和血小板的数量。为了实现这一…