LeetCode 3. 无重复字符的最长子串
题目描述
题意分析
在字符串中找出最长的一段连续字符，要求这段范围内每个字符最多出现一次，返回它的长度，不需要返回子串本身。子串必须连续，不能跳过中间字符来消除重复。
重复与否只针对选中的这段子串，不要求字符在整个字符串中只出现一次。空格、数字和符号也参与判断；空串的答案为
0，非空串至少可以选择一个字符。
解法：滑动窗口 + 最近出现位置
核心思路
[!blue]
用左右边界表示当前考察的连续区间，也就是滑动窗口。右边界
right每次向右加入一个字符，左边界left只在必须排除重复时右移。这样可以沿用上一轮已经检查过的结果，不必从每个起点重新扫描。加入当前字符
ch之前，窗口内已经没有重复，因此这一步只可能由ch引入重复。设它上一次出现在位置p：如果p还在窗口内，要同时保留当前位置的ch，左边界就必须越过p。移到p + 1恰好排除旧字符，其余字符仍然互不重复，再多移一步只会白白缩短窗口。如果旧位置已经在窗口左侧，它就不参与当前子串，左边界应保持不动。因此更新规则是
left = max(left, p + 1)。这里取最大值很重要：曾经为了排除其他重复字符移走的部分，不能因为读到较早的旧位置又重新放回窗口。代码用
last[ch]保存最近出现位置的下标加一，这样数组默认的0就能表示尚未出现，还能直接作为左边界的候选值。每轮先用旧记录更新left，用right - left + 1更新答案，最后再写入last[ch] = right + 1，避免把本次出现误当成旧记录。调整后的窗口是以当前
right结尾的最长合法子串：更靠左的起点会保留已经确认的重复，更靠右的起点只会更短。每个子串都有一个右端点，枚举全部右端点并保留最大的窗口长度，就能覆盖全局最优答案。
解题步骤
- 初始化数组
last、左边界left = 0和答案ans = 0，从左到右枚举right。- 读取当前字符的旧记录，令
left = max(left, last[ch])，使窗口恢复无重复。- 用
right - left + 1更新ans，保留遍历过程中出现过的最大长度。- 最后记录
last[ch] = right + 1，供后续字符使用；遍历结束返回ans。
代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] last = new int[128];
int left = 0;
int ans = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
left = Math.max(left, last[ch]);
ans = Math.max(ans, right - left + 1);
last[ch] = right + 1;
}
return ans;
}
}
func lengthOfLongestSubstring(s string) int {
var last [128]int
left, ans := 0, 0
for right := 0; right < len(s); right++ {
if last[s[right]] > left {
left = last[s[right]]
}
if length := right - left + 1; length > ans {
ans = length
}
last[s[right]] = right + 1
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，右指针遍历一次，每次只做常数次操作；左指针直接跳转，不需要回头扫描。
- 空间复杂度：$O(1)$，只使用固定大小的数组和几个变量。
关键点总结
[!green]
- 下标加一：旧字符在下标
i时，下一次遇到它可直接把左边界移到i + 1，同时利用数组默认的0表示未出现。- 只处理当前字符的重复：加入字符前窗口已经无重复，因此只需越过当前字符的旧位置，不必重新检查整个窗口。
- 窗口与答案分开维护：窗口是闭区间，长度为
right - left + 1；ans记录全局最大值，而不是最后一个窗口的长度。
易错点总结
[!yellow]
- 左边界不能回退：旧记录可能位于窗口外，直接赋值会把已排除的重复区间放回来，必须与当前
left取最大值。- 先用旧位置，再写新位置：如果先记录
right + 1再更新left，就会丢失旧位置，并把当前字符也排除在窗口外。- 闭区间长度要加一：只有一个字符时，
left = right，窗口长度应为1，不能写成right - left。- 不能只返回最后的窗口长度：最长子串可能在更早的位置结束，需要用
ans保存扫描过程中的最大长度。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 159. 至多包含两个不同字符的最长子串 | 中等 | 同样维护可扩张再收缩的字符窗口，原题允许两种字符重复，本题每种字符最多出现一次。 |
| 424. 替换后的最长重复字符 | 中等 | 同样追踪窗口内字符频次，原题允许替换预算，本题遇重复就必须调整左边界。 |
| 340. 至多包含 K 个不同字符的最长子串 | 中等 | 用滑动窗口维护字符频次和有效左边界；本题每个字符最多保留一次，该题允许最多 k 种字符。 |
| 904. 水果成篮 | 中等 | 用滑动窗口维护字符频次和有效左边界；本题每个字符最多保留一次，该题把两种水果限制转为两类元素窗口。 |
| 1100. 长度为 K 的无重复字符子串 | 中等 | 用滑动窗口维护字符频次和有效左边界；本题每个字符最多保留一次，该题固定窗口长度后统计无重复窗口。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！