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

【子串】3. 无重复的最长子串

3. 无重复的最长子串

难度:中等难度
力扣地址:https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

在这里插入图片描述

题目看起来简单,刷起来有好几个坑,特此记录一下,解法比官网的更加简单,可读性强。时间复杂度与空间复杂度与官方一样。

问题描述

给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

提示:

  • 0 <= s.length <= 5 * 1 0 4 10^4 104
  • s 由英文字母、数字、符号和空格组成。

问题分析

在这里插入图片描述

解决方法

结合示例 1,我做了一个详细的双指针移动 PPT 示意图。
在这里插入图片描述
在这里插入图片描述

解题代码

请小伙伴们结合上面的PPT进行理解,以下内容包括两种方法,第一种是基于哈希表,第二种使用 vector 替代哈希表,更快更节省资源(时间复杂度不变)

方法一:基于 unordered_map 记录历史 + 双指针一次遍历

class Solution {
public:int lengthOfLongestSubstring(string s) {// 用于记录每个字符最后一次出现的索引unordered_map<char, int> map;// 最终结果int result = 0;// 指针的开始位置,我们最终要求的无重复字符的最长子串的开始位置// 这个指针将会根据实际情况而移动,方向是一直向右int start = 0;// 一次遍历所有字符// 遍历过程中主要处理两个事情//   1. 移动 start 指针//   2. 计算现在已知的最长子串的长度for (int i = 0; i < s.length(); i++) {// 查找历史中该点auto tmp = map.find(s[i]);// 如果历史中存在数据,需要更新 start 的位置,表示新的最长子串的开始位置// 需要注意的是,更新后的start 必须越来越大,即向右边移动,避免 start 向左边移动if (tmp != map.end()) {start = max(tmp -> second + 1, start);}// 更新最后的结果,即最长子串的长度result = max(result, i - start + 1);// 写入/更新 s[i] 字符的索引map[s[i]] = i;}return result;}
};
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( ∑ ) O(\sum) O(),其中 ∑ \sum 表示字符集(即字符串中可以出现的字符),∣ ∑ \sum ∣ 表示字符集的大小。在本题中没有明确说明字符集,因此可以默认为所有 ASCII 码在 [0,128) 内的字符,即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符,而字符最多有 ∣ ∑ \sum ∣ 个,因此空间复杂度为 O(∣ ∑ \sum ∣)。

在这里插入图片描述

方法二:基于 vector 记录历史 + 双指针一次遍历

class Solution {
public:int lengthOfLongestSubstring(string s) {// 用于记录每个字符最后一次出现的索引vector<int> lastIndex(256, -1);// 最终结果int result = 0;// 指针的开始位置,我们最终要求的无重复字符的最长子串的开始位置int start = 0;// 一次遍历所有字符for (int end = 0; end < s.length(); end++) {// 更新 start 的位置if (lastIndex[s[end]] != -1) {start = max(lastIndex[s[end]] + 1, start);}// 更新最后的结果,即最长子串的长度result = max(result, end - start + 1);// 更新 s[end] 字符的索引lastIndex[s[end]] = end;}return result;}
};
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( ∑ ) O(\sum) O(),其中 ∑ \sum 表示字符集(即字符串中可以出现的字符),∣ ∑ \sum ∣ 表示字符集的大小。在本题中没有明确说明字符集,因此可以默认为所有 ASCII 码在 [0,128) 内的字符,即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符,而字符最多有 ∣ ∑ \sum ∣ 个,因此空间复杂度为 O(∣ ∑ \sum ∣)。
    在这里插入图片描述

总结

这道题目通过简单的双指针和哈希表的结合,可以高效地解决字符串中无重复字符的最长子串问题。这种方法的时间复杂度为O(n),因为每个字符在最坏情况下也只会被访问两次(一次作为结束字符,一次作为开始字符)。空间复杂度为O(1),因为哈希表的大小是固定的,最多为256个字符。

也正是基于这个原因,后面我们增加了使用 vector 提到哈希表,可以更加节省资源以及查找历史的时间。

Smileyan
2024.06.29 22:59

相关文章:

【子串】3. 无重复的最长子串

3. 无重复的最长子串 难度&#xff1a;中等难度 力扣地址&#xff1a;https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ 题目看起来简单&#xff0c;刷起来有好几个坑&#xff0c;特此记录一下&#xff0c;解法比官网的更加简单&…...

Scrapy中爬虫优化技巧分享

scrapy是一个非常有用的python爬虫框架&#xff0c;它可以帮助我们轻松地从不同的网站上获取数据。同时&#xff0c;scrapy也有越来越多的用户在使用它来爬取数据&#xff0c;因此&#xff0c;在使用scrapy的过程中&#xff0c;我们需要考虑如何优化我们的爬虫&#xff0c;以便…...

自然语言处理-BERT处理框架-transformer

目录 1.介绍 2.Transformer 2.1 引言 2.2 传统RNN网络的问题 2.3 整体架构 2.4 Attention 2.5 Self-Attention如何计算 3.multi-headed机制 4. BERT训练方法 1.介绍 BERT&#xff1a;当前主流的解决框架&#xff0c;一站式搞定NLP任务。&#xff08;解决一个NLP任务时的考虑…...

Kafka~消息系列问题解决:消费顺序问题解决、消息丢失问题优化(不能保证100%)

消息消费顺序问题 使用消息队列的过程中经常有业务场景需要严格保证消息的消费顺序&#xff0c;比如我们同时发了 2 个消息&#xff0c;这 2 个消息对应的操作分别对应的数据库操作是&#xff1a; 用户等级升级。根据用户等级下的订单价格 假如这两条消息的消费顺序不一样造…...

如何确保日常安全运维中的数据加密符合等保2.0标准?

等保2.0标准下的数据加密要求 等保2.0标准是中国信息安全等级保护制度的升级版&#xff0c;它对信息系统的安全保护提出了更为严格的要求。在日常安全运维中&#xff0c;确保数据加密符合等保2.0标准&#xff0c;主要涉及以下几个方面&#xff1a; 数据加密技术的选择&#xff…...

下一代的JDK - GraalVM

GraalVM是最近几年Java相关的新技术领域不多的亮点之一&#xff0c; 被称之为革命性的下一代JDK&#xff0c;那么它究竟有什么神奇之处&#xff0c;又为当前的Java开发带来了一些什么样的改变呢&#xff0c;让我们来详细了解下 下一代的JDK 官网对GraalVM的介绍是 “GraalVM 是…...

Java三方库-单元测试

文章目录 Junit注解常用类无参数单测带参数的单测 Junit 主要版本有4和5版本&#xff0c;注解不太一样&#xff0c; 4迁移5参考官方文档 主要记录下常用的一些操作 其他复杂操作见官网 https://junit.org/junit5/docs/current/user-guide/#overview-java-versions 引入5.9…...

p2p、分布式,区块链笔记: libp2p基础

通信密钥 noise::{Keypair, X25519Spec} X25519/Ed25519类似RSA 算法。Noise 用于设计和实现安全通信协议。它允许通信双方在没有预先共享密钥的情况下进行安全的密钥交换&#xff0c;并通过加密和身份验证保护通信内容。libp2p 提供了对 Noise 协议的原生支持&#xff0c;它允…...

企业本地大模型用Ollama+Open WebUI+Stable Diffusion可视化问答及画图

最近在尝试搭建公司内部用户的大模型,可视化回答,并让它能画图出来, 主要包括四块: Ollama 管理和下载各个模型的工具Open WebUI 友好的对话界面Stable Diffusion 绘图工具Docker 部署在容器里,提高效率以上运行环境Win10, Ollama,SD直接装在windows10下, 然后安装Docker…...

Unity学习笔记---调试

使用Log进行调试 使用Debug.Log方法可以将一些运行时信息打印到Console窗口中。 打印时间戳 //获取时间 Debug.Log(DateTime.Now.ToString());//打印毫秒级的时间 Debug.Log(((DateTime.Now.ToUniversalTime().Ticks - 621355968000000000) / 10000) * 0.001); 打印自定义文…...

Py之dashscope:dashscope的简介、安装和使用方法、案例应用之详细攻略

Py之dashscope&#xff1a;dashscope的简介、安装和使用方法、案例应用之详细攻略 目录 dashscope的简介 1、产品的主要特点和优势包括&#xff1a; dashscope的安装和使用方法 1、安装 2、使用方法 dashscope的案例应用 1、通义千问-Max&#xff1a;通义千问2.5系列 2…...

Go使用Gin框架开发的Web程序部署在Linux时,无法绑定监听Ipv4端口

最近有写一部分go语言开发的程序&#xff0c;在部署程序时发现&#xff0c;程序在启动后并没有绑定ipv4的端口&#xff0c;而是直接监听绑定ipv6的端口。 当我用netstat -antup | grep 3601查找我的gin服务启动的端口占用情况的时候发现&#xff0c;我的服务直接绑定了tcp6 &a…...

【图解大数据技术】Hadoop、HDFS、MapReduce、Yarn

【图解大数据技术】Hadoop、HDFS、MapReduce、Yarn HadoopHDFSHDFS架构写文件流程读文件流程 MapReduceMapReduce简介MapReduce整体流程 Yarn Hadoop Hadoop是Apache开源的分布式大数据存储与计算框架&#xff0c;由HDFS、MapReduce、Yarn三部分组成。广义上的Hadoop其实是指H…...

AGPT•intelligence:带你领略全新量化交易的风采

随着金融科技的快速发展&#xff0c;量化交易已经成为了投资领域的热门话题。越来越多的投资者开始关注和使用量化交易软件来进行投资决策。在市场上有许多量化交易软件可供选择。 Delaek&#xff0c;是一位资深的金融科技专家&#xff0c;在 2020年成立一家专注于数字资产量化…...

HarmonyOS Next开发学习手册——创建轮播 (Swiper)

Swiper 组件提供滑动轮播显示的能力。Swiper本身是一个容器组件&#xff0c;当设置了多个子组件后&#xff0c;可以对这些子组件进行轮播显示。通常&#xff0c;在一些应用首页显示推荐的内容时&#xff0c;需要用到轮播显示的能力。 针对复杂页面场景&#xff0c;可以使用 Sw…...

【计算机视觉】mmcv库详细介绍

文章目录 MMVC库概览特点和优势主要组件应用案例示例一:数据加载和处理示例二:模型训练和验证MMVC库概览 MMCV 是一个用于计算机视觉研究的开源库,它为各种视觉任务提供了底层的、高度优化的 API。该库涵盖了从数据加载到模型训练的各个方面,广泛应用于开源项目,如 MMDet…...

【面试系列】Go 语言高频面试题

欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;欢迎订阅相关专栏&#xff1a; ⭐️ 全网最全IT互联网公司面试宝典&#xff1a;收集整理全网各大IT互联网公司技术、项目、HR面试真题. ⭐️ AIGC时代的创新与未来&#xff1a;详细讲解AIGC的概念、核心技术、…...

React 扩展

文章目录 PureComponent1. 使用 React.Component&#xff0c;不会进行浅比较2. 使用 shouldComponentUpdate 生命周期钩子&#xff0c;手动比较3. 使用 React.PureComponent&#xff0c;自动进行浅比较 Render Props1. 使用 Children props&#xff08;通过组件标签体传入结构&…...

IT入门知识第八部分《云计算》(8/10)

目录 云计算&#xff1a;现代技术的新篇章 1. 云计算基础 1.1 云计算的起源和发展 云计算的早期概念 云计算的发展历程 1.2 云计算的核心特点 按需自助服务 广泛的网络访问 资源池化 快速弹性 按使用量付费 1.3 云计算的优势和挑战 成本效益 灵活性和可扩展性 维…...

Linux-笔记 全志T113移植正点4.3寸RGB屏幕笔记

目录 前言 线序整理 软件 显示调试 触摸调试 背光调试 前言 由于手头有一块4.3寸的RGB屏幕(触摸IC为GT1151)&#xff0c;正好开发板上也有40Pin的RGB接口&#xff0c;就想着给移植一下&#xff0c;前期准备工作主要是整理好线序&#xff0c;然后用转接板与杜邦线连接验证好…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...