当前位置：首页 > news >正文

字符串高频算法：无重复字符的最长子串

news 来源：原创 2025/5/20 10:23:19

题目

3. 无重复字符的最长子串 - 力扣（LeetCode）

解题思路

思路

方法: 滑动窗口

[!简单思路]
[^1]以示例一中的字符串 abcabcbb 为例，找出==从每一个字符开始的，不包含重复字符的最长子串==，其中最长的那个字符串即为答案。

对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：

以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb；
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
…

[!为什么可以使用滑动窗口]
依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第 k 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 r
k。那么当我们选择第 k+1 个字符作为起始位置时，首先从 k+1 到 r
k的字符显然是不重复的，并且由于少了原本的第 k 个字符，我们可以尝试继续增大 r
k，直到右侧出现了重复字符为止。
这样一来，我们就可以使用「滑动窗口」来解决这个问题了：

具体实现

分析Set方法在最长无重复子串问题中的应用

在本题中，使用了哈希集合的

has(value)：

- 用于检查集合中是否存在某个字符。在代码中，`occ.has(s.charAt(rk + 1))`用于判断当前字符是否已经存在于集合中。

add(value)：
- 用于将一个字符添加到集合中。在代码中，occ.add(s.charAt(rk + 1))用于将新遇到的字符添加到集合中。
delete(value)：
- 用于从集合中删除某个字符。在代码中，occ.delete(s.charAt(i - 1))用于在窗口左指针向右移动时，删除窗口左边界的字符。

滑动窗口法：
- 使用双指针（i 和 rk）来维护一个滑动窗口，确保窗口内的字符都是不重复的。
- i 表示窗口的左边界，rk 表示窗口的右边界。
Set的使用：
- occ 是一个Set，用于存储当前窗口中的字符。
- 在外层循环中，每次左指针i移动时，会删除前一个左边界字符。
- 内层循环中，右指针rk不断向右移动，直到遇到重复字符为止。

AC代码

var lengthOfLongestSubstring = function(s) {const occ = new Set(); // 创建哈希集合, 用户判断字符串是否重复const n = s.length; // 记录下s字符串的长度// 初始化右指针为 rk = -1, 表示右指针初始状态在字符串左边缘的左侧, 这样比较合理let rk = -1, ans = 0; // ans用来记录最终最大字符串的长度for(let i = 0; i < s.length; i++) {// 左指针向右移动一格, 移除一个字符if(i != 0) {occ.delete(s.charAt(i - 1));}// 右指针不越界并且右指针不是重复字符时while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {occ.add(s.charAt(rk + 1));++rk;}ans = Math.max(ans, rk - i + 1)}return ans;}

rk - i + 1：

当前窗口的长度是右指针 rk 减去左指针 i 加 1。这是因为索引是从 0 开始的，比如从索引 i 到 rk 的字符总共有 rk - i + 1 个。

Math.max(ans, rk - i + 1)：

ans 保存的是当前找到的最长无重复子串的长度。

Math.max 会比较 ans 和当前窗口的长度，取较大的值作为新的 ans，确保 ans 始终记录最长的窗口长度。

判断重复字符

使用哪种数据结构来判断 是否有重复的字符?
——JavaScript 中的 Set
在 JavaScript 中，要判断字符串中是否包含重复字符，可以使用 Set 数据结构。Set 是一种特殊的数据结构，它存入的值都是唯一的，不会有重复。

[!Set 判断字符串中是否有重复字符的步骤]

步骤：

1 将字符串转为字符数组
（将字符串拆分为单个字符组成的数组，以便逐个检查字符）
2 使用 Set 存储字符:
将字符数组中的每个字符存入 Set 中
3 比较 Set 的大小和原字符串的长度
如果 Set 的大小和原字符串的长度不同，说明存在重复字符，因为 Set 会自动去重.

字符串高频算法：无重复字符的最长子串

题目 3. 无重复字符的最长子串 - 力扣（LeetCode） 解题思路思路方法: 滑动窗口 [!简单思路] [^1]以示例一中的字符串 abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，其中最长的那个字符串即为答…...

编程日记 2025/5/20 10:23:19

集成学习（一）：从理论到实战(附代码)

一、引言在机器学习领域，打造一个独立、强大的算法是解决问题的关键。然而，集成学习提供了一种不同的视角：通过组合多个“弱”学习器来创建一个更强大的模型。本文探讨集成学习的思想、方法及其应用。二、机器学习 vs 集成学习思想传统…...

编程日记 2025/5/21 0:03:14

本地部署DeepSeek-R1模型（新手保姆教程）

背景最近deepseek太火了，无数的媒体都在报道，很多人争相着想本地部署试验一下。本文就简单教学一下，怎么本地部署。首先大家要知道，使用deepseek有三种方式： 1.网页端或者是手机app直接使用 2.使用代码调用API …...

编程日记 2025/5/18 22:57:34

轻松理解CSS中的float浮动元素

1.float:left，float:right可以让元素脱离原始文档流，也就是所谓的“浮动”，可以理解为元素漂浮在原本所占位置的上空，意思是元素漂浮起来了，不占原始文档流的空间。但是，别的元素可以感知到浮动元素的存在&…...

编程日记 2025/5/19 19:06:26

SOME/IP--协议英文原文讲解5

前言 SOME/IP协议越来越多的用于汽车电子行业中，关于协议详细完全的中文资料却没有，所以我将结合工作经验并对照英文原版协议做一系列的文章。基本分三大块： 1. SOME/IP协议讲解 2. SOME/IP-SD协议讲解 3. python/C举例调试讲解这一章节…...

编程日记 2025/5/14 11:16:41

如何优化频繁跳槽后的简历？

大家好！我是 [数擎 AI]，一位热爱探索新技术的前端开发者，在这里分享前端和 Web3D、AI 技术的干货与实战经验。如果你对技术有热情，欢迎关注我的文章，我们一起成长、进步！ 开发领域：前端开发 | A…...

编程日记 2025/5/19 14:00:19

存储异常导致的Oracle重大生产故障

📢📢📢📣📣📣 作者：IT邦德中国DBA联盟(ACDU)成员，10余年DBA工作经验 Oracle、PostgreSQL ACE CSDN博客专家及B站知名UP主，全网粉丝10万擅长主流Oracle、MySQL、PG、高斯…...

编程日记 2025/5/20 11:45:37

从家庭IP到全球网络资源的无缝连接：Cliproxy的专业解决方案

数字化时代，家庭IP作为个人或家庭接入互联网的门户，其重要性日益凸显。然而，要实现从家庭IP到全球网络资源的无缝连接，并享受高效、安全、稳定的网络访问体验，往往需要借助专业的代理服务。Cliproxy，作为业…...

编程日记 2025/5/20 23:36:34

java项目之金华学校社团管理系统源码(ssm+mysql)

项目简介金华学校社团管理系统实现了以下功能： 金华学校社团管理系统的主要使用者管理员对系统用户、公告信息进行管理。对社团信息进行管理，审核报名，统计社团报名结果等。学生维护个人信息，查看本校的社团信息，对…...

编程日记 2025/5/17 0:42:19

链表(LinkedList) 1

上期内容我们讲述了顺序表，知道了顺序表的底层是一段连续的空间进行存储(数组)，在插入元素或者删除元素需要将顺序表中的元素整体移动，时间复杂度是O(n)，效率比较低。因此，在Java的集合结构中又引入了链表来解决这一问…...

编程日记 2025/5/19 14:15:05

一、OSG学习笔记-编译开发环境

一、准备工作 1、osg3.6.4源码下载； openscenegraph/OpenSceneGraph at OpenSceneGraph-3.6.4 还有osg中所依赖的第三方库 2、cmake 下载安装好 3、Visual Studio 2019下载安装好二、cmake 编译构建项目这里下方1，2，两个先点击1&am…...

编程日记 2025/5/18 12:57:05

【Redis】Linux、Windows、Docker 环境下部署 Redis

一、Linux环境部署Redis 1、卸载 # 查看 Redis 是否还在运行 [appuserlocalhost redis]$ ps -ef|grep redis appuser 135694 125912 0 14:24 pts/1 00:00:00 ./bin/redis-server *:6379 appuser 135731 125912 0 14:24 pts/1 00:00:00 grep --colorauto redis# 停止…...

编程日记 2025/5/16 1:16:17

OSPF基础（3）：区域划分

OSPF的区域划分 1、区域产生背景路由器在同一个区域中泛洪LSA。为了确保每台路由器都拥有对网络拓扑的一致认知，LSDB需要在区域内进行同步。OSPF域如果仅有一个区域，随着网络规模越来越大，OSPF路由器的数量越来越多，这将导致诸…...

编程日记 2025/5/20 13:08:36

第436场周赛：按对角线进行矩阵排序、将元素分配给有约束条件的组、统计可以被最后一个数位整除的子字符串数目、最大化游戏分数的最小值

Q1、按对角线进行矩阵排序 1、题目描述给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵： 左下角三角形（包括中间对角线）的对角线按非递增顺序排序。右上角三角形的对角线按非递减顺序排序。 2、解题思路遍历所…...

编程日记 2025/5/19 4:05:11

DeepSeek vs. ChatGPT：不同的诞生时间，对人工智能发展的不同影响

DeepSeek vs. ChatGPT：不同的诞生时间，对人工智能发展的不同影响 ChatGPT 和 DeepSeek 诞生于不同的时间节点，代表了人工智能不同阶段的发展方向。它们在技术、应用以及对AI发展趋势的影响方面各有侧重。 1. 诞生时间与背景 ChatGPT&#x…...

编程日记 2025/5/15 13:35:48

chrome-base 如何实现一个BindOnce

考虑一个问题： worker_thread.task_runner()->PostDelayedTask(FROM_HERE, base::BindOnce(&Ref::Foo, ref, 1), base::Milliseconds(1000)); BindOnce 是如何实现的呢？ 翻看源码：base\functional\bind.h 写的非常简洁 // Bind a…...

编程日记 2025/5/17 3:15:25

代码随想录算法训练营day38

代码随想录算法训练营 —day38 文章目录代码随想录算法训练营前言一、322. 零钱兑换二维dp数组二、279.完全平方数二维dp数组三、139. 单词拆分多重背包背包问题总结问题类型递推公式遍历顺序前言今天是算法营的第38天，希望自己能够坚持下来！ 今日…...

编程日记 2025/5/19 9:57:24

对接DeepSeek

其实，整个对接过程很简单，就四步，获取key，找到接口文档，接口测试，代码对接。获取 KEY https://platform.deepseek.com/transactions 直接付款就是了（现在官网暂停充值2025年2月7日&#xff0…...

编程日记 2025/5/19 1:19:31

【学术投稿-第六届新材料与清洁能源国际学术会议（ICAMCE 2025）】组织与结构：HTML中的＜fieldset＞与＜legend＞标签解析

官网：www.icceam.com 简介第六届新材料与清洁能源国际学术会议（ICAMCE 2025）将于2025年2月21-23日在郑州隆重举行。清洁能源、新材料是当今工业发展中最重要、最有潜力的领域之一。而新型材料又是新能源的基础和保证。本会议主要围绕“清洁…...

编程日记 2025/5/15 0:45:03

网络安全行业的冬天

冬天已经来了，春天还会远吗？2022年10月28日，各个安全大厂相继发布了财报，纵观2022年前三季度9个月，三六零亏了19亿，奇安信亏了11亿，深信服亏了6亿，天融信亏了4亿，安恒亏了…...

编程日记 2025/5/20 14:44:13

PlantUml常用语法

PlantUml常用语法，将从类图、流程图和序列图这三种最常用的图表类型开始。类图基础语法在 PlantUML 中创建类图时，你可以定义类（Class）、接口（Interface）以及它们之间的关系，如继承&#…...

编程日记 2025/5/17 10:51:11

【开源免费】基于SpringBoot+Vue.JS网上服装商城（JAVA毕业设计）

本文项目编号 T 185 ，文末自助获取源码 \color{red}{T185，文末自助获取源码} T185，文末自助获取源码目录一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程四、功能截图五、文案资料5.1 选题背景5.2 国内…...

编程日记 2025/5/20 10:47:18

力扣LeetCode: 80 删除有序数组中的重复项Ⅱ

题目： 给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件…...

编程日记 2025/5/19 13:10:15

Linux之kernel(4)netlink通信

Linux内核(04)之netlink通信 Author: Once Day Date: 2023年1月3日一位热衷于Linux学习和开发的菜鸟，试图谱写一场冒险之旅，也许终点只是一场白日梦… 漫漫长路，有人对你微笑过嘛… 全系列文章可查看专栏: Linux内核知识_Once-Day的博客-…...

编程日记 2025/5/20 23:36:34

autMan奥特曼机器人-对接deepseek教程

一、安装插件ChatGPT 符合openai api协议的大模型均可使用此插件，包括chatgpt-4/chatgpt-3.5-turbo，可自定义服务地址和模型，指令：gpt，要求Python3.7以上，使用官方库https://github.com/openai/openai-pyt…...

编程日记 2025/5/20 14:55:34

Java 大视界 -- Java 大数据在智能政务中的应用与服务创新（78）

💖亲爱的朋友们，热烈欢迎来到青云交的博客！能与诸位在此相逢，我倍感荣幸。在这飞速更迭的时代，我们都渴望一方心灵净土，而我的博客正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识，也…...

编程日记 2025/5/20 6:16:02

RestTemplate Https 证书访问错误

错误信息 resttemplate I/O error on GET request for “https://21.24.6.6:9443/authn-api/v5/oauth/token”: java.security.cert.CertificateException: No subject alternative names present; nested exception is javax.net.ssl.SSLHandshakeException: java.security.c…...

编程日记 2025/5/19 23:50:16

自动化测试

import os import pyautogui# 将鼠标移动到屏幕坐标 (100, 100) 位置，移动时间为 1 秒 pyautogui.moveTo(100, 100, duration1)# 将鼠标从当前位置向右移动 50 像素，向下移动 50 像素，移动时间为 0.5 秒 pyautogui.moveRel(50, 50, duration0…...

编程日记 2025/5/19 4:27:08

【C编程问题集中营】使用数组指针时容易踩得坑

【C编程问题集中营】使用数组指针时容易踩得坑文章目录【C编程问题集中营】使用数组指针时容易踩得坑一、获取数组首地址二、应用场景举例2.1 正常场景2.2 异常场景三、总结一、获取数组首地址一维数组的首地址即数组第一个元素的指针，常用的获取一维数组首地…...

编程日记 2025/5/20 14:09:01

【分布式理论8】分布式调用之：四种IO模型

文章目录一. 四种IO模型1. 同步阻塞 IO（Blocking IO）2. 同步非阻塞 IO（Non-blocking IO）3. IO 多路复用（IO Multiplexing）4. 异步 IO（Asynchronous IO）在 RPC 中的作用5. 总结选择…...

编程日记 2025/5/18 5:20:43

MySQL 库建表数量有限制吗？

问：MySQL 库建表数量有限制吗？ 答：无限制官方文档： MySQL has no limit on the number of databases. The underlying file system may have a limit on the number of directories. MySQL has no limit on the number of tabl…...

编程日记 2025/5/20 23:32:37

使用OpenGL自己定义一个button，响应鼠标消息：掠过、点击、拖动

button需要有一个外观外观大小跟随窗口改变，采用纯色背景、纯色文字文字大小跟随窗口改变 button需要获得鼠标消息掠过鼠标掠过时 button 出现阴影，鼠标掠过后 button 阴影消失点击点击后进入相应事件拖动改变图标所在位置需要在g…...

编程日记 2025/5/20 23:29:28

基础入门-网站协议身份鉴权OAuth2安全Token令牌JWT值Authirization标头

知识点： 1、网站协议-http/https安全差异（抓包） 2、身份鉴权-HTTP头&OAuth2&JWT&Token 一、演示案例-网站协议-http&https-安全测试差异性 1、加密方式 HTTP：使用明文传输，数据在传输过程中可以被…...

编程日记 2025/5/20 13:06:42

【Python】元组

个人主页：GUIQU. 归属专栏：Python 文章目录 1. 元组的本质与基础概念1.1 不可变序列的意义1.2 元组与数学概念的联系 2. 元组的创建方式详解2.1 标准创建形式2.2 单元素元组的特殊处理2.3 使用 tuple() 函数进行转换 3. 元组的基本操作深入剖析3.1 索引操…...

编程日记 2025/5/16 7:16:04

深度求索与DeepSeek-R1：探索人工智能的新纪元

深度求索与DeepSeek-R1：探索人工智能的新纪元引言在当今快速发展的科技领域，尤其是人工智能（AI）方面，每隔一段时间就会出现一款革命性的产品或技术，彻底改变我们对这一领域的认知。2025年初&#xff0c…...

编程日记 2025/5/20 23:19:27

java: framework from BLL、DAL、IDAL、MODEL、Factory using oracle

oracel 21c sql: -- 创建 School 表 CREATE TABLE School (SchoolId CHAR(5) NOT NULL,SchoolName NVARCHAR2(500) NOT NULL,SchoolTelNo VARCHAR2(8) NULL,PRIMARY KEY (SchoolId) );CREATE OR REPLACE PROCEDURE addschool(p_school_id IN CHAR,p_school_name IN NVARCHAR2,p…...

编程日记 2025/5/20 22:48:05

题目