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

[LeetCode 题3] 没有重复字符的最长的子字符串

问题描述

  • 输入:一个字符串 s
  • 输出:最长的无重复字符的子串的长度。

示例

  1. 输入: s = "abcabcbb" 输出: 3 解释: 最长的无重复字符的子串是 "abc",长度为 3。

  2. 输入: s = "bbbbb" 输出: 1 解释: 最长的无重复字符的子串是 "b",长度为 1。

  3. 输入: s = "pwwkew" 输出: 3 解释: 最长的无重复字符的子串是 "wke",长度为 3。

约束条件

  • 0 <= s.length <= 5 * 10^4
  • 字符串 s 可以包含英文字符、数字、符号和空格。

解决方案

我们可以使用滑动窗口的方法来解决这个问题。滑动窗口是一种常用的算法技巧,用于处理数组或字符串中的子区间问题。具体步骤如下:

通过这种方法,我们可以高效地找到最长的无重复字符子串,时间复杂度为 O(n),其中 n 是字符串 s 的长度。空间复杂度为 O(min(n, m)),其中 m 是字符集的大小(对于 ASCII 字符集,m 为 128)。

  1. 使用两个指针 left 和 right 来表示当前窗口的左右边界。
  2. 使用一个哈希集合(Set)来存储当前窗口内的字符,以便快速检查字符是否重复。
  3. 移动 right 指针扩展窗口,直到遇到重复字符。
  4. 当遇到重复字符时,移动 left 指针收缩窗口,直到窗口内没有重复字符。
  5. 在每次移动 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

    详细解释

  6. 初始化变量

    • left 和 right 分别表示滑动窗口的左右边界,初始值都为 0。
    • maxLength 用于记录最长无重复字符子串的长度,初始值为 0。
    • charSet 是一个集合,用于存储当前窗口内的字符。
  7. 滑动窗口

    • 使用 while 循环遍历字符串 s,直到 right 指针到达字符串末尾。
    • 如果当前字符 s[right] 不在 charSet 中:
      • 将该字符加入 charSet
      • 更新 maxLength 为当前窗口的长度 right - left + 1
      • 移动 right 指针。
    • 如果当前字符 s[right] 已经在 charSet 中:
      • 从 charSet 中移除 s[left]
      • 移动 left 指针。
  8. 返回结果

    • 返回 maxLength 作为最长无重复字符子串的长度。

相关文章:

[LeetCode 题3] 没有重复字符的最长的子字符串

问题描述 输入&#xff1a;一个字符串 s。输出&#xff1a;最长的无重复字符的子串的长度。 示例 输入: s "abcabcbb" 输出: 3 解释: 最长的无重复字符的子串是 "abc"&#xff0c;长度为 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引领新潮流

在移动应用市场中&#xff0c;App下载量是衡量应用受欢迎程度和市场表现的重要指标。然而&#xff0c;对于许多开发者而言&#xff0c;如何精准统计App下载量却是一个不小的挑战。幸运的是&#xff0c;如今有了一款专业的App全渠道统计服务商——Xinstall&#xff0c;它能够帮助…...

ijkMediaPlayer+ TextureView 等比全屏播放视频(避免拉伸)

TextureView默认以fitxy的方式加载surface数据&#xff0c;如果需要等比全屏播放视频&#xff0c;避免拉伸&#xff0c;可以采用Matrix对TextureView进行变换 废话不多说&#xff0c;直接上代码 public class BaseIjkPlayer implements TextureView.SurfaceTextureListener{/…...

【RS】GEE(Python):数据处理

在前面的章节中&#xff0c;我们已经学习了如何加载影像数据。现在&#xff0c;让我们进一步探讨如何在 Google Earth Engine (GEE) 中进行数据处理。数据处理通常包括图像预处理、裁剪、过滤、重采样等操作。 栅格影像的处理 栅格影像处理包括了裁剪、波段选择、重采样、合成…...

非线性磁链观测器推导

<div id"content_views" class"htmledit_views"><p id"main-toc"><strong>目录</strong></p> 电机方程 电压方程 磁链方程 定义状态变量和输出变量 非线性观测器方程 电角度的计算--锁相环 锁相环调参 电机…...

什么时机用mysql,什么时机用redis,什么时机用本地内存

mysql 的 buffer pool 也是存在内存中&#xff0c;redis 的数据也是存在内存中&#xff0c;为什么不直接存在 mysql 里&#xff1f; 1、数据结构和访问方式 Redis 是一个内存数据库&#xff0c;专门为高效的读写性能而设计。它支持多种数据结构&#xff08;如字符串、列表、哈…...

Redis八股

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

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 的实现

封装&#xff1a; std::queue 在底层容器的基础上 提供了封装。默认情况下&#xff0c;std::queue 使用 std::deque 作为其底层容器&#xff0c;但也可以配置为使用 std::list 或 其他符合要求的容器 时间复杂度&#xff1a; 入队和出队操作 通常是 常数时间复杂度&#xff08…...

【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 仓库中的子模块&#xff08;submodules&#xff09;。这个命令在 Git 仓库中包含对其他 Git 仓库作为依赖时…...

面试问我LLM中的RAG,咱就是说秒过!!!

前言 本篇文章涉及了 RAG 流程中的数据拆分、向量化、查询重写、查询路由等等&#xff0c;在做 RAG 的小伙伴一定知道这些技巧的重要性。推荐仔细阅读&#xff0c;建议收藏&#xff0c;多读几遍&#xff0c;好好实践。 本文是对检索增强生成&#xff08;Retrieval Augmented …...

python程序操作pdf

python代码进行多个图片合并为pdf&#xff1a; #python代码进行多个图片合并为pdf&#xff1a; from PIL import Image from fpdf import FPDF import osdef images_to_pdf(image_paths, output_pdf, quality85):"""将多个图片合并为一个PDF文件&#xff0c;并…...

【Python报错】ImportError: DLL load failed while importing _network: 找不到指定的模块。

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

外包干了5天,技术明显退步

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

正则表达式 | Python、Julia 和 Shell 语法详解

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

JavaScript全面指南(一)

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

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...