【算法训练-双指针】最长无重复子串(数组)

废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是最长无重复子串或最长无重复子数组,这类题目出现频率还是很高的。
在这里插入图片描述

最长无重复子数组

先来看看数组数据结构的题目

题干

在这里插入图片描述

输入:
[2,3,4,5]返回值:
4说明:
[2,3,4,5]是最长子数组  
输入:
[2,2,3,4,8,99,3]返回值:
5说明:
最长子数组为[2,3,4,8,99]  

解题思路

整体目标就是获取最大的无重复滑动窗口

  1. 双指针标识数组或字符串的位置,右指针可以理解为放大窗口指针,左指针可以理解为缩小窗口指针
  2. 定义一个set用来存储元素位置对应的值
  3. 右指针先行,如果一直无重复就一直开拓窗口并更新max值,否则移动左指针缩小窗口,直到将重复值缩到窗口以外。

如下图所示:
在这里插入图片描述

解题代码

Java实现的代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param arr int整型一维数组 the array* @return int整型*/public int maxLength (int[] arr) {// 1 判断入参是否为空列表if (arr.length == 0) {return 0;}// 2 定义返回结果最大值和左右指针以及滑动窗口集合int max = 0;int left = 0;int right = 0;Set<Integer> set = new HashSet<>();// 3 滑动窗口移动并在无重复时计算最大值while (left < arr.length && right < arr.length) {// 1 无重复,右指针继续移动,重新计算最大值if (!set.contains(arr[right])) {set.add(arr[right++]);max = Math.max(max, right - left);} else {// 2 有重复,左指针继续移动,直到将重复元素移出集合set.remove(arr[left++]);}}return max;}
}

时间复杂度为O(N),因为遍历了数组;空间复杂度为O(N),借助了HashSet的存储空间

最长无重复子串

先来看字符串数据结构的题目

题干

在这里插入图片描述

解题思路

同上

解题代码

class Solution {public int lengthOfLongestSubstring(String s) {// 1 判断入参是否为空列表if (s.length() == 0) {return 0;}// 2 定义返回结果最大值和左右指针以及滑动窗口集合int max = 0;int left = 0;int right = 0;Set<Character> set = new HashSet<>();// 3 滑动窗口移动并在无重复时计算最大值while (left < s.length() && right < s.length()) {// 1 无重复,右指针继续移动,重新计算最大值if (!set.contains(s.charAt(right))) {set.add(s.charAt(right++));max = Math.max(max, right - left);} else {// 2 有重复,左指针继续移动,直到将重复元素移出集合set.remove(s.charAt(left++));}}return max;}
}

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

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

相关文章

Android studio 软件git使用

在 test 分支添加的方法 , 现在切换到 master分支 总共 2 个分支 , 当前的分支是 test 出现了 先试一下 force checkout , 尝试之后发现 , 你更改没有带过来 , 以为哪个类在master分支没有 , 所以这边也没有 , 切回分支 test 发现之前的跟改没有 , 这样即可以找回 继续切换…

土豆叶病害识别(图像连续识别和视频识别)

效果视频&#xff1a;土豆叶病害识别&#xff08;Python代码&#xff0c;pyTorch框架&#xff0c;视频识别&#xff09;_哔哩哔哩_bilibili 代码运行要求&#xff1a;Torch库>1.13.1&#xff0c;其它库无版本要求 1..土豆叶数据集主要包好三种类别&#xff08;Early_Blight…

Redis下载与安装

文章目录 Redis简介下载&#xff0c;安装和配置&#xff08;cmd&#xff09;图形化工具 Redis 简介 下载&#xff0c;安装和配置&#xff08;cmd&#xff09; 开启redis服务 1.在解压出来的文件夹中打开cmd 2.输入 redis-server.exe redis.windows.conf即可开启服务 可以看到…

用香港服务器域名需要备案吗?

​  在选择服务器的时候&#xff0c;很多人会考虑使用香港服务器。香港服务器的一个优势就是不需要备案。不管是虚拟主机还是云主机&#xff0c;无论是个人网站还是商业网站&#xff0c;都不需要进行备案手续。 域名实名认证 虽然不需要备案&#xff0c;但使用香港服务器搭建…

Jetpack Compose UI架构

Jetpack Compose UI架构 引言 Jetpack Compose是我职业生涯中最激动人心的事。它改变了我工作和问题思考的方式&#xff0c;引入了易用且灵活的工具&#xff0c;几乎可轻松实现各种功能。 早期在生产项目中尝试了Jetpack Compose后&#xff0c;我迅速着迷。尽管我已有使用Co…

【jvm】双亲委派机制

目录 一、说明二、工作原理三、优势四、图示 一、说明 1.java虚拟机对class文件采用的是按需加载的方式&#xff0c;当需要使用该类时才会将它的class文件加载到内存生成class对象 2.加载某个类的class文件时&#xff0c;java虚拟机采用双亲委派模式&#xff0c;即把请求交给由…

Spring Authorization Server入门 (十六) Spring Cloud Gateway对接认证服务

前言 之前虽然单独讲过Security Client和Resource Server的对接&#xff0c;但是都是基于Spring webmvc的&#xff0c;Gateway这种非阻塞式的网关是基于webflux的&#xff0c;对于集成Security相关内容略有不同&#xff0c;且涉及到代理其它微服务&#xff0c;所以会稍微比较麻…

怎么把pdf转换成jpg格式?

怎么把pdf转换成jpg格式&#xff1f;在我们日常的办公过程中&#xff0c;PDF文件是一个经常被使用来传输文件的格式。它能够确保我们的文件内容不会混乱&#xff0c;并以更加完美的方式呈现出来。然而&#xff0c;PDF文件也存在一些缺陷。例如&#xff0c;它无法直接编辑&#…

React+Typescript从请求数据到列表渲染

我们在项目src目录下创建一个目录 叫 pages 在里面创建一个组件叫 list.tsx 这里 我启动了自己的java项目 创建接口 你们就也需要弄几个自己的接口做测试 然后 list.tsx 编写代码如下 import * as React from "react";export default class hello extends React.C…

【seaweedfs】3、f4: Facebook’s Warm BLOB Storage System 分布式对象存储的冷热数据

论文地址 Facebook的照片、视频和其他需要可靠存储和快速访问的二进制大型对象(BLOB)的语料库非常庞大&#xff0c;而且还在继续增长。随着BLOB占用空间的增加&#xff0c;将它们存储在我们传统的存储系统-- Haystack 中变得越来越低效。为了提高我们的存储效率(以Blob的有效复…

基于安卓的考研助手系统app 微信小程序

&#xff0c;设计并开发实用、方便的应用程序具有重要的意义和良好的市场前景。HBuilder技术作为当前最流行的操作平台&#xff0c;自然也存在着大量的应用服务需求。 本课题研究的是基于HBuilder技术平台的安卓的考研助手APP&#xff0c;开发这款安卓的考研助手APP主要是为了…

计算机系统真题

计算机系统真题 考点计算机系统存储体系磁盘调度算法 考点 计算机系统 PC找到指令&#xff0c;存储到IR中 根据ID分析指令的操作&#xff0c;并执行指令,AR访问操作数 A pc存指令的地址 内存按照字节编址&#xff1a; 在统一单位&#xff0c;转换一下&#xff1a; 3x2的平方 …

Unix时间戳

江科大学习记录 Unix时间戳 Unix 时间戳&#xff08;Unix Timestamp&#xff09;定义为从UTC/GMT的1970年1月1日0时0分0秒开始所经过的秒数&#xff0c;不考虑闰秒时间戳存储在一个秒计数器中&#xff0c;秒计数器为32位/64位的整型变量世界上所有时区的秒计数器相同&#xf…

HTML番外篇(五)-移动端适配

一、媒体查询 1.认识媒体查询 媒体查询是一种提供给开发者针对不同设备需求进行定制化开发的一个接口。 你可以根据设备的类型&#xff08;比如屏幕设备、打印机设备&#xff09;或者特定的特性(比如屏幕的宽度)来修改你的页面。 媒体查询的使用方式主要有三种&#xff1a;…

算法笔记:球树

1 KD树的问题 算法笔记&#xff1a;KD树_UQI-LIUWJ的博客-CSDN博客 在kd树中&#xff0c;导致性能下降的最核心因素是因为kd-tree中被分割的子空间是一个个的超方体&#xff0c;而求最近邻时使用的是欧式距离&#xff08;超球&#xff09;。超方体与超球体相交的可能性是极高…

【VsCode】SSH远程连接Linux服务器开发,搭配cpolar内网穿透实现公网访问(1)

文章目录 前言1、安装OpenSSH2、vscode配置ssh3. 局域网测试连接远程服务器4. 公网远程连接4.1 ubuntu安装cpolar内网穿透4.2 创建隧道映射4.3 测试公网远程连接 5. 配置固定TCP端口地址5.1 保留一个固定TCP端口地址5.2 配置固定TCP端口地址5.3 测试固定公网地址远程 前言 远程…

SpringBootWeb案例 Part3

目录 1. 新增员工 1.1 需求 1.2 接口文档 1.3 思路分析 PostMapping RequestBody //把前端传递的JSON数据填充到实体类中 1.4 功能开发 1.5 功能测试 1.6 前后端联调 2. 文件上传 2.1 文件上传简介 Spring中提供了一个API&#xff1a;MultipartFile&#xff0c;使…

爬虫逆向实战(二十一)-- 某某点集登录与获取数据

登录 一、数据接口分析 主页地址&#xff1a;某某点集 1、抓包 通过抓包可以发现登录接口是phonePwdLogin 2、判断是否有加密参数 请求参数是否加密&#xff1f; 通过查看“载荷”模块可以发现有pwd和sig两个加密参数 请求头是否加密&#xff1f; 无响应是否加密&#x…

144. 二叉树的前序遍历-C++

题目来源&#xff1a;力扣 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,2,3]示例 2&#xff1a; 输入&#xff1a;root [] 输出&#xff1a;[] 代码实现&#xff1a; class Solution { public:vector<int> preorderTraversal(TreeNo…

深入理解linux内核--程序的执行

可执行文件 在第一章中我们把进程定义为“执行上下文”。这就意味着进行特定的计算需要收集必要的信息&#xff0c;包括所访问的页&#xff0c;打开的文件&#xff0c;硬件寄存器的内容等等。 可执行文件是一个普通文件&#xff0c;它描述了如何初始化一个新的执行上下文&…