本文详解如何将滑动窗口求无重复字符最长子串的算法从低效集合遍历优化为基于哈希表索引的真正线性解法，显著降低运行时开销，避免冗余删除与重复查找。
本文详解如何将滑动窗口求无重复字符最长子串的算法从低效集合遍历优化为基于哈希表索引的真正线性解法，显著降低运行时开销，避免冗余删除与重复查找。
原始实现虽在理论上具有 O(n) 时间复杂度，但实际性能瓶颈明显：每次遇到重复字符时，都依赖 while s[r] in longest 循环逐个移除左侧字符并更新集合——该 in 操作虽平均 O(1)，但在最坏情况下（如大量连续重复）会触发多次哈希探查与内存操作；更关键的是，longest.remove(s[l]) 和 l += 1 的迭代过程本质上是“盲目收缩”，未利用字符位置信息，导致大量无效计算。此外，调试用的 print() 语句在大规模输入下会严重拖慢执行（如题中 6558ms 即主要源于此）。
真正的优化核心在于用空间换确定性时间：不再用集合动态维护窗口内字符，而是用哈希表 char_index 显式记录每个字符最后出现的索引位置。这样，当右指针 r 遇到已存在的字符 char 时，我们可立即判断该重复是否发生在当前窗口内——只需检查 char_index[char] >= l。若成立，说明该重复字符位于窗口 [l, r] 中，则直接将左指针 l 跳跃至 char_index[char] + 1，跳过所有中间无效状态，避免逐个收缩。
以下是优化后的标准实现：
class Solution(object):
def lengthOfLongestSubstring(self, s):
char_index = {} # 键：字符；值：该字符最近一次出现的索引
max_length = 0
l = 0
for r, char in enumerate(s):
# 若字符已存在且其上一次位置仍在当前窗口内，则收缩左边界
if char in char_index and char_index[char] >= l:
l = char_index[char] + 1
# 更新字符最新位置（无论是否重复，均覆盖为当前索引）
char_index[char] = r
# 当前窗口长度为 r - l + 1，实时更新最大值
max_length = max(max_length, r - l + 1)
return max_length
该实现具备以下优势：
✅ 严格单次遍历：r 从左到右仅扫描一次，l 只增不减，无嵌套循环；
✅ O(1) 平均查找与更新：哈希表读写均为常数时间，无 while 收缩开销；
✅ 逻辑清晰可验证：l 始终指向当前有效窗口起点，char_index 提供精确位置依据；
✅ 无调试副作用：移除所有 print，适配 LeetCode 高频测试用例。
⚠️ 注意事项：
- 不可省略
char_index[char] >= l判断。若仅写if char in char_index，可能错误地将窗口外的历史重复（如"abba"中第二个'a'对应第一个'a'已被滑出）当作冲突处理，导致l回退； -
char_index[char] = r必须放在判断之后、更新max_length之前，确保窗口[l, r]始终满足无重复（因l已根据历史位置校准）； - 空字符串或单字符输入均可自然处理，无需额外边界判断。
总结而言，本题优化的本质是从「模拟窗口收缩过程」升维至「基于位置索引的窗口跳跃调整」。它不仅将实际运行时间从数千毫秒降至百毫秒级（LeetCode 典型提交耗时
