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

Leetcode 剑指 Offer II 016. 不含重复字符的最长子字符串

题目难度: 中等

原题链接

今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例  1:

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

示例 2:

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

示例 3:

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

示例 4:

  • 输入: s = “”
  • 输出: 0

提示:

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

题目思考

  1. 如何通过一次遍历得出结果?
  2. 如果统计当前子字符串的字符种类?

解决方案

思路

  • 分析题目, 一个最简单的思路就是暴力法: 固定子字符串起点, 然后往后扩展, 因为不能含有重复, 所以可以使用集合统计当前子字符串的字符种类, 直到发现重复字符或者到终点停止, 取最长的子字符串作为结果. 但这样需要两重遍历, 时间复杂度达到 O(N*C) (C 是字符的种类数目, 因为找到重复就会停下来, 所以不是 N^2), 不是很优
  • 基于暴力法进行分析, 假设当前子字符串起点是 start, 发现重复字符的位置是 end, 然后对应的该字符上个下标是 dup, 显然start <= dup < end
  • 此时暴力法的做法是将 start+1 重新开始遍历子字符串, 但这样做完全没有必要, 因为以[start+1, dup]中的任一下标作为起点的字符串肯定都会在 end 处停下来, 因为找到了重复的(end 和 dup), 而且这些子字符串长度必然小于以 start 为起点的
  • 所以更优化的做法是将起点向后遍历到 dup+1, 从字符集合中移除遍历过程中的字符, 然后将 dup+1 作为新的起点, 终点继续从 end 处开始遍历, 直到再次遇到重复字符, 重复上述步骤即可
  • 这样起点和终点都只需要遍历一遍, 相比暴力法有所优化
  • 以上就是典型的滑动窗口的思想, 通常做法就是维护双指针代表窗口起点和终点, 然后根据当前窗口是否满足要求来进行不同的处理
  • 下面的代码对必要步骤有详细的解释, 方便大家理解

复杂度

  • 时间复杂度 O(N): 起点和终点都只需要遍历一遍
  • 空间复杂度 O(1): 只使用了几个变量

代码

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 滑动窗口+当前字符集合, 时刻更新resstart = 0res = 0v = set()for end in range(len(s)):c = s[end]if c in v:# 发现重复了, start向后遍历找dup下标(即上一个c的下标)while start < end and s[start] != c:v.remove(s[start])start += 1# 此时dup = start, 需要将dup+1作为新的起点start += 1else:# 没有重复, 将当前字符加入字符集合中v.add(c)# 最大子字符串长度就是最大的字符集合的长度, 当然此处也可以用end-start+1代替res = max(res, len(v))return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我

http://www.lryc.cn/news/20746.html

相关文章:

  • TCP 的演化史-sack 与 reordering metric
  • 【Spring6】| Spring的入门程序、集成Log4j2日志框架
  • 包子凑数(完全背包)
  • Spring超级全家桶,学完绝对是惊艳面试官的程度
  • Redis主要数据类型
  • 【Linux | ELK 8.2】搭建ELKB集群Ⅰ—— 实验环境说明和搭建Elasticsearch集群
  • 不同情况下*p和*p的区别(指针)
  • Vuex基础语法
  • 刚上岸字节测试开发岗,全网最真实的大厂面试真题
  • Mac监控键盘输入并执行动作
  • Transformer输出张量的值全部相同?!
  • 港科夜闻|全国政协副主席梁振英先生率香港媒体高管团到访香港科大(广州)...
  • XML调用 CAPL Test Function
  • Linux网络配置(NAT)
  • 数据结构——第二章 线性表(8)——线性表总结
  • 3.7寸按键翻页工牌
  • 西北工业大学大学物理(II)选填解析2019-2020期末
  • [计算机网络(第八版)]第一章 概述(章节测试/章节作业)
  • 华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典
  • 电子科技大学数据库与软件工程三
  • 华为开源自研AI框架昇思MindSpore数据变换:Transforms
  • 软件测试之边界值测试法
  • 【华为OD机试模拟题】用 C++ 实现 - 最近的点(2023.Q1)
  • Qt windeployqt.exe 打包qml
  • 【人脸识别】CurricularFace:自适应课程学习人脸识别损失函数
  • springmvc之rest风格(RESTFUL)
  • django项目实战十四(django+bootstrap实现增删改查)进阶混合数据使用modelform上传
  • 2023年CDGA考试模拟题库(1-100)
  • HTML常用基础内容总结
  • Gorm-学习笔记