哈希算法题目：最长不含重复字符的子字符串 题目描述 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 例如： 输入 s = "abcabcbb" ，输出 3 ，最长无重复字符子串是 "abc" 。 输入 s = "bbbbb" ，输出 1 ，最长子串是 "b" 。 输入 s = "pwwkew" ，输出 3 ，最长子串是 "wke" 或 "kew" 。 解题思路 这个问题可以用 滑动窗口 和 哈希表 结合解决。 滑动窗口：用两个指针 left 和 right 表示当前考察的子串范围，确保窗口内无重复字符。 哈希表：记录每个字符 最近一次出现的位置 ，用于快速判断重复和移动 left 指针。 步骤详解 步骤1：初始化 创建哈希表 charIndex ，键是字符，值是该字符最近一次出现的下标。 初始化 left = 0 ， maxLen = 0 。 遍历字符串， right 从 0 到 len(s)-1 。 步骤2：检查重复 当 right 指向新字符 s[right] 时： 如果 s[right] 在 charIndex 中存在，且其上次出现的位置 index >= left ，说明它在当前窗口内重复了。 此时需要收缩窗口：将 left 移动到该重复字符上次出现位置的右边一位，即 left = index + 1 。这样可以立即排除重复。 步骤3：更新哈希表和最大长度 无论是否重复，都更新 charIndex[s[right]] = right ，记录当前字符的最新位置。 计算当前窗口长度 right - left + 1 ，更新 maxLen = max(maxLen, 当前长度) 。 步骤4：遍历结束 遍历完成后， maxLen 即为答案。 示例推演 以 s = "abcabcbb" 为例： | right | s[ right ] | charIndex (更新后) | left | 操作说明 | maxLen | |-------|----------|-------------------|------|----------|---------| | 0 | 'a' | {'a':0} | 0 | 无重复 | 1 | | 1 | 'b' | {'a':0, 'b':1} | 0 | 无重复 | 2 | | 2 | 'c' | {'a':0, 'b':1, 'c':2} | 0 | 无重复 | 3 | | 3 | 'a' | {'a':3, 'b':1, 'c':2} | 1 | 'a'重复，left移动到1 | 3 | | 4 | 'b' | {'a':3, 'b':4, 'c':2} | 2 | 'b'重复，left移动到2 | 3 | | 5 | 'c' | {'a':3, 'b':4, 'c':5} | 3 | 'c'重复，left移动到3 | 3 | | 6 | 'b' | {'a':3, 'b':6, 'c':5} | 5 | 'b'重复，left移动到5 | 3 | | 7 | 'b' | {'a':3, 'b':7, 'c':5} | 7 | 'b'重复，left移动到7 | 3 | 最终 maxLen = 3 。 复杂度分析 时间复杂度：O(n)，n 为字符串长度，每个字符被访问一次。 空间复杂度：O(min(m, n))，m 是字符集大小（例如 ASCII 为 128），哈希表存储最多 m 个字符。 关键点总结 哈希表记录字符最近下标，实现 O(1) 时间判断重复。 滑动窗口通过移动 left 跳过重复位置，避免重新扫描。 只有重复字符出现在窗口内（ index >= left ）才需要移动 left 。