[LeetCode 题3] 没有重复字符的最长的子字符串
问题描述
- 输入:一个字符串
s
。 - 输出:最长的无重复字符的子串的长度。
示例
-
输入:
s = "abcabcbb"
输出:3
解释: 最长的无重复字符的子串是"abc"
,长度为 3。 -
输入:
s = "bbbbb"
输出:1
解释: 最长的无重复字符的子串是"b"
,长度为 1。 -
输入:
s = "pwwkew"
输出:3
解释: 最长的无重复字符的子串是"wke"
,长度为 3。
约束条件
0 <= s.length <= 5 * 10^4
- 字符串
s
可以包含英文字符、数字、符号和空格。
解决方案
我们可以使用滑动窗口的方法来解决这个问题。滑动窗口是一种常用的算法技巧,用于处理数组或字符串中的子区间问题。具体步骤如下:
通过这种方法,我们可以高效地找到最长的无重复字符子串,时间复杂度为 O(n),其中 n 是字符串 s
的长度。空间复杂度为 O(min(n, m)),其中 m 是字符集的大小(对于 ASCII 字符集,m 为 128)。
- 使用两个指针
left
和right
来表示当前窗口的左右边界。 - 使用一个哈希集合(Set)来存储当前窗口内的字符,以便快速检查字符是否重复。
- 移动
right
指针扩展窗口,直到遇到重复字符。 - 当遇到重复字符时,移动
left
指针收缩窗口,直到窗口内没有重复字符。 - 在每次移动
right
指针时,更新最长子串的长度。function lengthOfLongestSubstring(s) {let left = 0;let right = 0;let maxLength = 0;const charSet = new Set();while (right < s.length) {if (!charSet.has(s[right])) {// 如果当前字符不在集合中,将其加入集合charSet.add(s[right]);// 更新最长子串的长度maxLength = Math.max(maxLength, right - left + 1);// 移动右指针right++;} else {// 如果当前字符在集合中,移除左指针指向的字符charSet.delete(s[left]);// 移动左指针left++;}}return maxLength; }// 示例用法 console.log(lengthOfLongestSubstring("abcabcbb")); // 输出: 3 console.log(lengthOfLongestSubstring("bbbbb")); // 输出: 1 console.log(lengthOfLongestSubstring("pwwkew")); // 输出: 3
详细解释
-
初始化变量:
left
和right
分别表示滑动窗口的左右边界,初始值都为 0。maxLength
用于记录最长无重复字符子串的长度,初始值为 0。charSet
是一个集合,用于存储当前窗口内的字符。
-
滑动窗口:
- 使用
while
循环遍历字符串s
,直到right
指针到达字符串末尾。 - 如果当前字符
s[right]
不在charSet
中:- 将该字符加入
charSet
。 - 更新
maxLength
为当前窗口的长度right - left + 1
。 - 移动
right
指针。
- 将该字符加入
- 如果当前字符
s[right]
已经在charSet
中:- 从
charSet
中移除s[left]
。 - 移动
left
指针。
- 从
- 使用
-
返回结果:
- 返回
maxLength
作为最长无重复字符子串的长度。
- 返回
相关文章:
[LeetCode 题3] 没有重复字符的最长的子字符串
问题描述 输入:一个字符串 s。输出:最长的无重复字符的子串的长度。 示例 输入: s "abcabcbb" 输出: 3 解释: 最长的无重复字符的子串是 "abc",长度为 3。 输入: s "bbbbb" 输出: 1 解释: 最长的无重复字…...
YoloDotNet 在工业检测中的应用详解
文章目录 一、数据收集与标注二、模型选择与训练三、检测流程设计四、结果评估与优化五、与工业生产线集成一、数据收集与标注 在工业检测中,首先需要收集大量的相关工业产品图像数据。这些数据应涵盖不同的产品类型、缺陷种类以及各种可能的生产状态。例如,对于电子产品的检…...

DataFrame增删改数据
目录 准备数据 DataFrame添加列 直接添加列数据 使用insert添加列数据 DataFrame删除行列 准备数据 删除行 删除列 DataFrame数据去重 准备数据 import pandas as pd df pd.read_csv("../data/b_LJdata.csv") df DataFrame添加列 直接添加列数据 1&…...

一站式解决App下载量统计,Xinstall引领新潮流
在移动应用市场中,App下载量是衡量应用受欢迎程度和市场表现的重要指标。然而,对于许多开发者而言,如何精准统计App下载量却是一个不小的挑战。幸运的是,如今有了一款专业的App全渠道统计服务商——Xinstall,它能够帮助…...
ijkMediaPlayer+ TextureView 等比全屏播放视频(避免拉伸)
TextureView默认以fitxy的方式加载surface数据,如果需要等比全屏播放视频,避免拉伸,可以采用Matrix对TextureView进行变换 废话不多说,直接上代码 public class BaseIjkPlayer implements TextureView.SurfaceTextureListener{/…...
【RS】GEE(Python):数据处理
在前面的章节中,我们已经学习了如何加载影像数据。现在,让我们进一步探讨如何在 Google Earth Engine (GEE) 中进行数据处理。数据处理通常包括图像预处理、裁剪、过滤、重采样等操作。 栅格影像的处理 栅格影像处理包括了裁剪、波段选择、重采样、合成…...

非线性磁链观测器推导
<div id"content_views" class"htmledit_views"><p id"main-toc"><strong>目录</strong></p> 电机方程 电压方程 磁链方程 定义状态变量和输出变量 非线性观测器方程 电角度的计算--锁相环 锁相环调参 电机…...
什么时机用mysql,什么时机用redis,什么时机用本地内存
mysql 的 buffer pool 也是存在内存中,redis 的数据也是存在内存中,为什么不直接存在 mysql 里? 1、数据结构和访问方式 Redis 是一个内存数据库,专门为高效的读写性能而设计。它支持多种数据结构(如字符串、列表、哈…...

Redis八股
缓存 缓存穿透 当查询一个不存在的数据,mysql查询不到数据,无法写入缓存,导致每次都请求数据库 解决方法 缓存空数据,当查询结果未空,将结果进行缓存。 简单但是会消耗内存,而且会出现不一致情况。布隆…...

vue3--通用 popover 气泡卡片组件实现
背景 在日常开发中,我们一般都是利用一些诸如:element-ui、element-plus、ant-design等组件库去做我们的页面或者系统 这些对于一些后台管理系统来说是最好的选择,因为后台管理系统其实都是大同小异的,包括功能、布局结构等 但是对于前台项目,比如官网、门户网站这些 …...

Bluetooth Channel Sounding中关于CS Step及Phase Based Ranging相应Mode介绍
目录 BLE CS中Step定义 BLE CS中交互的数据包/波形格式 BLE CS中Step的不同Mode BLE CS中Step的执行过程 Mode0介绍 Mode0 步骤的作用 Mode0步骤的执行过程 Mode0步骤的执行时间 Mode0步骤的时间精度要求 Mode2介绍 Mode2步骤的作用和执行过程 Mode2步骤的执行时间 B…...
简易STL实现 | Queue 的实现
封装: std::queue 在底层容器的基础上 提供了封装。默认情况下,std::queue 使用 std::deque 作为其底层容器,但也可以配置为使用 std::list 或 其他符合要求的容器 时间复杂度: 入队和出队操作 通常是 常数时间复杂度(…...

【hot100-java】LRU 缓存
链表篇 灵神题解 class LRUCache {private static class Node{int key,value;Node prev,next;Node (int k,int v){keyk;valuev;}}private final int capacity;//哨兵节点private final Node dummynew Node(0,0);private final Map<Integer,Node> keyToNode new HashMap&l…...

Centos7安装ZLMediaKit
一 获取代码 git clone https://gitee.com/xia-chu/ZLMediaKit cd ZLMediaKit git submodule update --init git submodule update --init 命令用于初始化和更新 Git 仓库中的子模块(submodules)。这个命令在 Git 仓库中包含对其他 Git 仓库作为依赖时…...

面试问我LLM中的RAG,咱就是说秒过!!!
前言 本篇文章涉及了 RAG 流程中的数据拆分、向量化、查询重写、查询路由等等,在做 RAG 的小伙伴一定知道这些技巧的重要性。推荐仔细阅读,建议收藏,多读几遍,好好实践。 本文是对检索增强生成(Retrieval Augmented …...
python程序操作pdf
python代码进行多个图片合并为pdf: #python代码进行多个图片合并为pdf: from PIL import Image from fpdf import FPDF import osdef images_to_pdf(image_paths, output_pdf, quality85):"""将多个图片合并为一个PDF文件,并…...

【Python报错】ImportError: DLL load failed while importing _network: 找不到指定的模块。
【Python报错】ImportError: DLL load failed while importing _network: 找不到指定的模块。 问题描述报错原因解决方案参考 问题描述 此段Python代码(在Conda环境下运行)昨天还能运行,但在我手痒更新conda(我有罪)之…...

外包干了5天,技术明显退步
我是一名本科生,自2019年起,我便在南京某软件公司担任功能测试的工作。这份工作虽然稳定,但日复一日的重复性工作让我逐渐陷入了舒适区,失去了前进的动力。两年的时光匆匆流逝,我却在原地踏步,技术没有丝毫…...

正则表达式 | Python、Julia 和 Shell 语法详解
正则表达式在网页爬虫、脚本编写等众多任务中都有重要的应用。为了系统梳理其语法,以及 Python、Julia 和 Shell 中与正则表达式相关的工具,本篇将进行详细介绍。 相关学习资源:编程胶囊。 基础语法 通用语法 在大多数支持正则表达式的语…...

JavaScript全面指南(一)
🌈个人主页:前端青山 🔥系列专栏:JavaScript篇 🔖人终将被年少不可得之物困其一生 依旧青山,本期给大家带来JavaScript篇专栏内容:JavaScript全面指南(一) 1、介绍一下JS的内置类型有哪些? 基本数据类型…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...