算法系列之滑动窗口
算法系列之滑动窗口
题目
给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

解题思路
使用滑动窗口算法
滑动窗口算法的核心思想是在一个给定的序列(如数组或字符串)上定义一个窗口,该窗口可以根据特定的条件进行动态调整。窗口的大小可以固定,也可以根据问题的需求动态变化。在滑动过程中,通过不断更新窗口的边界和内部元素的状态,我们能够高效地获取所需的信息,如最大、最小子序列和,满足特定条件的子序列等。
想象一个在序列上滑动的窗口,就像一个移动的框,它可以从序列的起始位置开始,每次移动一个单位(或根据具体情况移动多个单位)。在每一步移动中,窗口会 “吸入” 新的元素,同时 “吐出” 离开窗口范围的元素。通过对窗口内元素的实时计算和记录,我们可以在不遍历整个序列的情况下,快速找到满足特定条件的子序列。
- 算法原理
- 初始化:设置左右指针left和right,通常都指向数据结构的起始位置。
- 窗口滑动:
- 扩展右边界:通常先移动right指针来扩展窗口的右边界,直到窗口内的元素不再满足特定条件或right指针到达数据结构的末尾。
- 收缩左边界:在窗口不满足条件时,移动left指针来收缩窗口的左边界,直到窗口内的元素重新满足条件。
- 记录结果:在窗口滑动的过程中,记录下满足条件的中间结果(如最大值、最小值、子串长度等)。
- 重复步骤:重复步骤2和3,直到right指针遍历完整个数据结构。
获取某个字符串中不重复的字符长度,如abfhdasdrbch
//abfhdasdrbch//思路// 索引-字符-不重复字符串-重新开始//0-a-a (开始位index=0即a)//1-b-ab//2-f-abf//3-h-abfh//4-d-abfhd//5-a-bfhda(a重复了,所以需要重新开始,新的开始位,index=1即b)//6-s-bfhdas//7-d-asd (又重复了,新的开始位,index=5即a)//8-r-asdr//9-b-asdrb
public static int getBig(String s){//最大长度int max=0;//下一段不重复开始发起始索引号int startIndex=0;//字符对应最新的索引号HashMap<Character, Integer> characterHashMap = new HashMap<Character, Integer>();int length = s.length();for (int i = 0; i < length; i++) {Integer charIndex = characterHashMap.get(s.charAt(i));if (charIndex!=null){// 如果字符已经存在于哈希表中,并且其位置在窗口内,则移动左边界startIndex=Math.max(charIndex+1,startIndex);}characterHashMap.put(s.charAt(i),i);max=Math.max(max,i-startIndex+1);}return max;
}相关文章:
算法系列之滑动窗口
算法系列之滑动窗口 题目 给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。 示例 1:输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2:输入: s "bbbbb"…...
【C#】详解C#中的内存管理机制
文章目录 前言一、C#内存管理的基本机制(1)托管堆(Managed Heap)(2)垃圾回收(Garbage Collection)(3)栈内存 二、 开发者需要主动管理的场景(1&am…...
C/S架构与B/S架构
一、定义与核心区别 C/S架构(Client/Server,客户端/服务器) 客户端需安装专用软件(如QQ、企业ERP系统),直接与服务器通信。服务器端通常包括数据库和业务逻辑处理1。特点:客户端承担部分计算任务…...
《DeepSeek MoE架构下,动态专家路由优化全解析》
在人工智能飞速发展的当下,模型架构的创新与优化始终是推动技术进步的关键力量。DeepSeek的混合专家模型(MoE)架构,以其独特的设计理念和卓越的性能表现,在大模型领域崭露头角。而其中的动态专家路由优化技术ÿ…...
Android双亲委派
下面是一份 Android 类加载器双亲委派机制的时序图示例,描述了当应用调用 loadClass() 时,各个加载器之间的委派过程。 #mermaid-svg-rBdlhpD2uRjBPiG8 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mer…...
go语言因为前端跨域导致无法访问到后端解决方案
前端服务8080访问后端8081这端口显示跨域了 ERROR Network Error AxiosError: Network Error at XMLHttpRequest.handleError (webpack-internal:///./node_modules/axios/lib/adapters/xhr.js:116:14) at Axios.request (webpack-internal:///./node_modules/axios/lib/core/A…...
Jmeter使用介绍
文章目录 前言Jmeter简介安装与配置JDK安装与配置JMeter安装与配置 打开JMeter方式一方式二 设置Jmeter语言为中文方法一(仅一次性)方法二(永久设置成中文) Jmeter文件常用目录 元件与组件元件组件元件的作用域元件的执行顺序第一个案例添加线程组添加 H…...
【商城实战(13)】购物车价格与数量的奥秘
【商城实战】专栏重磅来袭!这是一份专为开发者与电商从业者打造的超详细指南。从项目基础搭建,运用 uniapp、Element Plus、SpringBoot 搭建商城框架,到用户、商品、订单等核心模块开发,再到性能优化、安全加固、多端适配…...
Spring使用@Scheduled注解的参数详解
在现代Java开发中,定时任务是一个常见的需求。Spring框架提供了Scheduled注解,让我们能够以简单、直观的方式定义和管理这些定时任务。接下来,我们来深入探讨这个注解的使用,以及它的参数都有哪些含义和作用。 Scheduled注解可以…...
【网络】HTTP协议、HTTPS协议
HTTP与HTTPS HTTP协议概述 HTTP(超文本传输协议):工作在OSI顶层应用层,用于客户端(浏览器)与服务器之间的通信,B/S模式 无状态:每次请求独立,服务器不保存客户端状态(通过Cookie/Session扩展状态管理)。基于TCP:默认端口80(HTTP)、443(HTTPS),保证可靠传输。请…...
【Windows下Gitbook快速入门使用】
Windows下Gitbook快速入门使用 1 工具安装1.1 Node.js下载安装1.1 环境变量1.2 npm配置1.3 安装gitbook 2 gitbook使用2.1 gitbook 无法执行2.2 gitbook常用命令 Gitbook是一个软件,使用Git和Markdown来编排书本; GitBook helps you pushlish beautiful …...
创建Electron35 + vue3 + electron-builder项目,有很过坑,记录过程
环境: node v20.18.0 npm 11.1.0 用到的所有依赖: "dependencies": {"core-js": "^3.8.3","vue": "^3.2.13","vue-router": "^4.5.0"},"devDependencies": {"ba…...
FPGA 实验报告:四位全加器与三八译码器仿真实现
目录 安装Quartus软件 四位全加器 全加器、半加器 半加器: 全加器: 四位全加器电路图 创建项目 半加器 全加器 四位全加器 代码实现 半加器 全加器 四位全加器 三八译码器 创建项目 代码展示 modelsim仿真波形图 四位全加器 三八译码…...
动态规划详解(二):从暴力递归到动态规划的完整优化之路
目录 一、什么是动态规划?—— 从人类直觉到算法思维 二、暴力递归:最直观的问题分解方式 1. 示例:斐波那契数列 2. 递归树分析(以n5为例) 3. 问题暴露 三、第一次优化:记忆化搜索(Memoiza…...
前端学习——HTML
HTML VSCode常用快捷键HTML标签文本标签列表标签表格Form表单表单元素 块元素与行内元素新增标签 VSCode常用快捷键 代码格式化:ShiftAltF 向上或向下移动一行:AltUp或AltDown 快速复制一行代码:ShiftAltUp或者ShiftAltDown 快速替换&#x…...
12.【线性代数】——图和网络
十二 图和网络(线性代数的应用) 图 g r a p h { n o d e s , e d g e s } graph\{nodes, edges\} graph{nodes,edges}1.关联矩阵2. A A A矩阵的零空间,求解 A x 0 Ax0 Ax0 电势3. A T A^T AT矩阵的零空间,电流总结电流图结论 …...
[环境搭建篇] Windows 环境下如何安装repo工具
Windows 环境下如何安装repo工具 1. 安装前置依赖2. 配置Repo引导脚本方法一:通过Gitee镜像安装(推荐)方法二:通过清华镜像安装 3. 解决依赖问题4. 初始化Repo仓库5. 常见问题解决 前言: 在Windows环境下安装Repo工具需…...
LeetCode 热题 100_字符串解码(71_394_中等_C++)(栈)
LeetCode 热题 100_字符串解码(71_394) 题目描述:输入输出样例:题解:解题思路:思路一(栈): 代码实现代码实现(栈):以思路一为例进行调…...
「DataX」数据迁移-IDEA运行DataX方法总结
背景 业务需求希望把Oracle数据库中的数据,迁移至MySql数据库中,因为需要迁移全量和增量的数据,所以希望想用数据迁移工具进行操作。 经过一些调研查询,最终打算使用DataX进行数据的迁移。 DataX简单介绍 DataX 是阿里云 DataW…...
【 <一> 炼丹初探:JavaWeb 的起源与基础】之 Servlet 过滤器:实现请求的预处理与后处理
<前文回顾> 点击此处查看 合集 https://blog.csdn.net/foyodesigner/category_12907601.html?fromshareblogcolumn&sharetypeblogcolumn&sharerId12907601&sharereferPC&sharesourceFoyoDesigner&sharefromfrom_link <今日更新> 一、过滤器&…...
从零到上线:用Vue3+AntV G2快速搭建企业级数据大屏
从零到上线:用Vue3AntV G2快速搭建企业级数据大屏 在数字化转型浪潮中,数据可视化已成为企业决策的重要支撑。想象这样一个场景:会议室里,高管们围坐在大屏前,实时业务数据通过动态图表清晰呈现,关键指标一…...
Python异常处理最佳实践:从原理到实践
Python异常处理最佳实践:从原理到实践 1. 背景与动机 在Python编程中,异常处理是一个重要的编程实践。良好的异常处理可以使程序更加健壮,提高代码的可维护性和可读性。然而,许多开发者在处理异常时存在一些常见的问题,…...
小红书数据采集系统深度探索:从技术原理到实战落地
小红书数据采集系统深度探索:从技术原理到实战落地 【免费下载链接】XiaohongshuSpider 小红书爬取 项目地址: https://gitcode.com/gh_mirrors/xia/XiaohongshuSpider 在当今数据驱动的时代,小红书作为内容丰富的社交平台,其数据价值…...
OpenClaw+GLM-4.7-Flash:智能爬虫与数据分析
OpenClawGLM-4.7-Flash:智能爬虫与数据分析 1. 为什么需要智能爬虫与数据分析 最近我在做一个小型竞品分析项目时,遇到了一个典型的数据收集困境:需要从20多个竞品网站抓取产品功能描述、定价策略和用户评价,然后整理成结构化数…...
从Buck到三电平:软开关DC-DC变换器的Simulink建模与双闭环控制仿真
1. 从Buck到三电平:电力电子技术的进化之路 记得我第一次接触DC-DC变换器时,Buck电路就像是一道必须跨过的门槛。这个经典的降压电路结构简单,却蕴含着电力电子最基础的设计思想。但随着项目需求的提升,传统Buck电路在高压大功率场…...
SDXL 1.0电影级绘图工坊高清图集:1536px输出下4K显示器全屏无像素感展示
SDXL 1.0电影级绘图工坊高清图集:1536px输出下4K显示器全屏无像素感展示 1. 项目简介 SDXL 1.0电影级绘图工坊是一款基于Stable Diffusion XL Base 1.0模型的AI绘图工具,专门为RTX 4090显卡优化设计。这个工具充分利用了4090显卡的24G大显存࿰…...
s2-pro GPU算力适配实战:显存优化部署让语音合成延迟降低40%
s2-pro GPU算力适配实战:显存优化部署让语音合成延迟降低40% 1. 专业语音合成新选择 s2-pro是Fish Audio开源的专业级语音合成模型镜像,它让高质量的文本转语音变得触手可及。与普通语音合成工具不同,s2-pro支持通过参考音频复用音色&#…...
CLIP-GmP-ViT-L-14图文匹配工具实战:新闻配图与标题语义一致性自动检测
CLIP-GmP-ViT-L-14图文匹配工具实战:新闻配图与标题语义一致性自动检测 你有没有遇到过这种情况?看到一篇新闻,标题写得挺吸引人,但配图却让人摸不着头脑——标题说“科技创新”,配图却是风景照;标题讲“经…...
OpenClaw+GLM-4.7-Flash极客玩法:浏览器自动化与RPA任务融合
OpenClawGLM-4.7-Flash极客玩法:浏览器自动化与RPA任务融合 1. 当OpenClaw遇见GLM-4.7-Flash 去年冬天的一个深夜,我正为重复性的网页数据抓取任务头疼不已。Selenium脚本频繁因页面结构变化而崩溃,每次都需要人工介入调整。直到发现OpenCl…...
当NB-IoT遇上同步轨道卫星:GEO场景下的定时关系增强全指南(基于3GPP Release 17最新规范)
GEO卫星场景下NB-IoT定时关系增强技术解析 1. GEO卫星通信与NB-IoT的技术融合挑战 地球静止轨道(GEO)卫星通信与窄带物联网(NB-IoT)技术的结合,为全球物联网覆盖提供了革命性解决方案。GEO卫星位于地球赤道上空35,786公…...
