LeetCode 3：无重复字符的最长子串
题目描述
难度：中等
给定一个字符串 s，找出其中不包含重复字符的最长连续子串，并返回它的长度。
示例 1
输入：s = "abcabcbb"
输出：3
解释："abc"、"bca" 和 "cab" 都是长度为 3 的无重复字符子串。
示例 2
输入：s = "bbbbb"
输出：1
示例 3
输入：s = "pwwkew"
输出：3
解释：最长无重复字符子串之一是 "wke"。子串要求字符在原字符串中连续。
数据范围
0 <= s.length <= 10^5。s由英文字母、数字、符号和空格组成。
题解
思路：滑动窗口与哈希表
使用 [start, end] 表示当前窗口，并保证窗口内的字符互不重复。
end逐个扫描字符串，加入新的字符。start记录窗口的左边界，只向右移动。mp记录每个字符最近一次出现的下标加一。ans记录遍历过程中发现的最大窗口长度。
遇到字符 alpha := s[end] 时，如果它曾经出现过，取出 v := mp[alpha]。当 v > start 时，说明上次出现的位置仍在当前窗口内，将 start 移动到 v，就能排除旧字符。
随后用 end - start + 1 更新答案，并将 mp[alpha] 更新为 end + 1。
为什么保存下标加一
假设字符上次出现在下标 i。再次遇到它时，窗口左边界需要移动到 i + 1。直接保存 i + 1，就可以用 start = v 完成更新。
例如 "abcabcbb" 扫描到下标 3 的 a 时，mp['a'] 为 1。将 start 从 0 移动到 1 后，窗口变为 "bca"，其中的字符仍然互不重复。
为什么要判断 v > start
哈希表保存了扫描过的所有字符的位置，其中可能包含已经离开窗口的字符。只有旧位置仍在窗口内时，才需要移动左边界。
以 "abba" 为例：
- 扫描到第二个
b时，将start移动到下标2，窗口为"b"。 - 扫描到最后一个
a时，mp['a']为1，小于当前start = 2。 - 保持左边界为
2，得到合法窗口"ba"，最终答案为2。
如果直接赋值 start = v，左边界就会退回下标 1，形成包含重复字符的窗口 "bba"。因此左边界必须保持单调递增。
正确性说明
每轮处理前，已有窗口中的字符互不重复。加入新字符后，唯一可能新增的重复来自该字符的历史位置。
如果旧位置在窗口内，将左边界移动到旧位置后一位，即可去除重复；如果旧位置在窗口外，当前窗口可以直接扩展。这样的更新保留了以 end 结尾的最长合法窗口。
遍历所有右边界并取最大窗口长度，就能得到整个字符串的最长无重复字符子串长度。
复杂度分析
- 时间复杂度：平均
O(n)。右边界遍历字符串一次，每轮只进行常数次哈希表查询、更新与比较。 - 空间复杂度：
O(min(n, |Σ|))，其中|Σ|表示字符集大小。这份代码使用byte作为键，最多保存 256 个不同的值，因此在固定字节字符集下也可以记为O(1)。
Go 代码
func lengthOfLongestSubstring(s string) int {
ans := 0
n := len(s)
mp := make(map[byte]int)
for start, end := 0, 0; end < n; end++ {
alpha := s[end]
if v, ok := mp[alpha]; ok {
if v > start {
start = v
}
}
if end-start+1 > ans {
ans = end - start + 1
}
mp[alpha] = end + 1
}
return ans
}
这份实现按字节处理字符串，适用于本题的字符范围。处理中文、表情等 Unicode 内容时，可以转换为 []rune，并使用 map[rune]int 按 Unicode 码点维护窗口。
小结
滑动窗口通过移动左边界排除重复字符，哈希表提供最近一次出现的位置。理解 mp 保存下标加一，以及 start 始终向右移动这两个细节，就能准确维护窗口并在线性时间内求出答案。