考察点:滑动窗口 + 哈希/数组记录字符最后出现位置;窗口收缩条件;为什么是 O(n) 而非 O(n^2);边界处理。属编程题。
要点:
>= left),则把 left 跳到「该字符上次位置 + 1」以剔除重复,保证窗口合法性。每步用哈希记录字符最新下标。 def lengthOfLongestSubstring(s):
last = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return best
left、right 各访问一次,时间 O(n);哈希表大小受字符集限制,空间 O(字符集)(ASCII 即 O(128))。left 会回跳,但 left、right 都只单向不减地前进,总移动次数 ≤ 2n。题目与答案就在本页;收藏、批注和错题重练在应用内