31.无重复字符的最长子串
题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
- 输入: s = "abcabcbb"
- 输出: 3
- 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
- 输入: s = "bbbbb"
- 输出: 1
- 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
- 输入: s = "pwwkew"
- 输出: 3
- 解释:
- 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
- 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示:
- 0 <= s.length <= 5 * 104
- s 由英文字母、数字、符号和空格组成
思路
这道题主要用到思路是：滑动窗口
什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
leftIndex = 0
rightIndex = 0
# pwwkew
# "abcabcbb"
result = 0
while rightIndex < len(s):
index = s[leftIndex: rightIndex].find(s[rightIndex])
if index >= 0:
leftIndex += index + 1
rightIndex += 1
result = max(result, rightIndex - leftIndex)
return result
这个实现的时间复杂度是O(n²)，显然不满足。
可以使用Set或者HashMap进行优化:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
leftIndex = 0
rightIndex = 0
result = 0
data = set()
while rightIndex < len(s):
while s[rightIndex] in data:
data.remove(s[leftIndex])
leftIndex += 1
data.add(s[rightIndex])
rightIndex += 1
result = max(result, rightIndex - leftIndex)
return result
class Solution {
fun lengthOfLongestSubstring(s: String): Int {
val window = HashSet<Char>() // 窗口状态：当前窗口内的字符集合
var left = 0
var maxLen = 0
for (right in s.indices) {
val c = s[right]
// 收缩条件：新字符已在窗口中 → 窗口非法 → 从左侧不断移出，直到重复消失
while (c in window) {
window.remove(s[left])
left++
}
// 此时窗口已合法，纳入新字符
window.add(c)
// 窗口合法，更新最长长度（在 while 之后）
maxLen = maxOf(maxLen, right - left + 1)
}
return maxLen
}
}
方法一遇到重复时是一格一格移动 left。可以用 HashMap 记录每个字符最后出现的下标，遇到重复时让 left 一步跳到位，省去逐格移动。
class Solution {
fun lengthOfLongestSubstring(s: String): Int {
// 字符 -> 它最近一次出现的下标
val lastIndex = HashMap<Char, Int>()
var left = 0
var maxLen = 0
for (right in s.indices) {
val c = s[right]
// 如果 c 出现过，且上次出现位置在当前窗口内（>= left），
// 直接把 left 跳到「上次出现位置的下一格」
if (lastIndex.containsKey(c) && lastIndex[c]!! >= left) {
left = lastIndex[c]!! + 1
}
lastIndex[c] = right // 更新该字符的最新位置
maxLen = maxOf(maxLen, right - left + 1)
}
return maxLen
}
}
- 时间复杂度：O(n)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!