type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个字符串
s ,请你找出其中不含有重复字符的 最长子串的长度。示例 1:
示例 2:
示例 3:

说明:
0 <= s.length <= 5 * 10000
s由英文字母、数字、符号和空格组成
解法一:滑动窗口 + Set
[l, r] 是当前无重复的窗口。右指针 r 每次尝试加入新字符- 如果
ch没在窗口里,它就能被安全地加入窗口,长度更新;
- 如果
ch已经在窗口里,说明窗口里出现了重复。左指针l右移,从左边一点点收,同时把滑出窗口的字符从set里移除,直到集合中没有字符与ch冲突。
集合始终是窗口内的字符集,窗口内永远保持“无重复”。
复杂度:
- 时间:
O(N)(每个字符最多进/出集合各一次)
- 空间:
O(min(N, |Σ|))(Σ 为字符集合;集合最多装下当前窗口大小)
解法二:滑动窗口 + 哈希(推荐)
上一种解法在遇到冲突时,一步步收缩左端。
其实我们可以“跳着走”:维护一个哈希
last[c] 记录字符 c 上次出现的下一个位置(即 last[c] = 上次出现的索引 + 1)。当右指针
r 看到了字符 ch:- 如果
ch没出现过,那就正常更新长度;
- 如果
ch出现过,意味着当前窗口[l, r]里包含了旧的ch,那左端至少要跳到last[ch]才能避开,于是l = max(l, last[ch])直接跳过重复段。其中max很关键,避免左端倒退。
复杂度:
- 时间:
O(N)(每个位置访问/更新一次字典)
- 空间:
O(min(N, |Σ|))(字典最多记录每个字符的最近位置)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-3-无重复字符的最长子串
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
Understanding Recursion: Functions That Call Themselves
下一篇
[Leetcode 4] 两个排序数组的中位数