【leetcode】3. Longest Substring Without Repeating Characters无重复字符的最长子串
题意理解
给定字符串 s，找其中不含重复字符的最长子串的长度。比如 "abcabcbb" 答案是 3（"abc"），"bbbbb" 答案是 1，空串返回 0。
这题典型滑动窗口：维护一段「窗口内字符互不重复」的子串，尽量拉长右边界，冲突时收缩左边界。
思路
查找无重复的字符子串，然后滑动窗口。暴力版每次右移一格，重复就左移一格；优化版在发现重复时，左指针直接跳到重复字符上次出现位置的下一格，避免无效左移。
初次解
每次滑动一格窗口。isUnique 用 s.count(ch) 判断子串里有没有重复字符——能跑，但每个字符都扫一遍子串，很慢。
class Solution:
def isUnique(self, s: str) -> bool:
for ch in s:
if s.count(ch) > 1:
return False
else:
continue
return True
def lengthOfLongestSubstring(self, s: str) -> int:
i,j,Max=0,0,0
j+=1
while j <= len(s):
if self.isUnique(s[i:j]):
print(s[i:j],"is Unique",i,j)
Max=max(j-i,Max)
j+=1
else:
i+=1
return Max
复杂度
- 暴力：
isUnique对子串 O(k)，窗口最多 O(n²) 次，整体约 O(n³)。 - 空间 O(1)（不算
print调试输出）。
成果
第一次优化
右指针 j 每步前进，用 st.find(s[j+1]) 看新字符是否已在当前窗口里；若在，左指针 i 跳过重复段，直接对齐到重复字符后一位。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if(len(s)==1):
return 1
i,j,Max=0,0,0
while j <= len(s):
st = s[i:j+1]
if(j+1 < len(s)):
index = st.find(s[j+1])
if index > -1:
i+=(index+1)
j+=1
Max=max(j-i+1,Max)
else:
break
return Max
优化思路与复杂度
- 不再每次重新
count全子串，重复时左边界一次跳到位。 find仍是线性，最坏仍偏慢；更稳的做法是用set或dict记窗口内字符及最后下标，均摊 O(n)。- 空间：当前实现 O(1) 额外空间（切片
st会临时占内存）。
成果
这版在 LeetCode 上能 AC。若还要再抠性能，可以把 st.find 换成哈希表维护「字符 → 最近下标」，窗口右扩时更新、冲突时 i = max(i, last[ch] + 1)，那就是标准滑动窗口写法了。
用 dict 时，右指针每走一步把 s[j] 记入表；若 s[j] 已存在且下标 ≥ i，说明窗口内重复，把 i 推到重复位置之后。全程每个字符最多进出窗口各一次，时间 O(n)，空间 O(min(n, 字符集大小))。Python 刷题到这步就够用了。
版权声明: 本文首发于 指尖魔法屋-【leetcode】3. Longest Substring Without Repeating Characters无重复字符的最长子串（https://blog.thinkmoon.cn/post/721-notes-leetcode-longest-substring/） 转载或引用必须申明原指尖魔法屋来源及源地址！