滑动窗口算法：3行代码之差，性能相差10倍的两种解法之争

面试官在白板上写下"最长无重复子串"，候选人的手指悬在键盘上方——这道题每年让多少工程师在屏幕前卡住，又有多少人在事后才想起：原来窗口的边界移动藏着这么多细节。

问题现场：一道经典题的隐藏复杂度

给定字符串"abcabcbb"，要求找出最长的不含重复字符的连续子串。表面看是双指针遍历，实则暗藏陷阱：右指针只管扩张，左指针何时收缩？遇到重复字符是跳一步还是直接跳转？

两种解法就此分道扬镳。

解法一：暴力哈希的O(n²)陷阱

最直观的思路：右指针每走一步，用HashSet检查窗口内是否重复。一旦发现重复，左指针逐步右移，直到冲突消失。

while (r < s.length()) {if (set.contains(s.charAt(r))) {set.remove(s.charAt(l++));  // 左指针蜗牛式爬行} else {set.add(s.charAt(r++));max = Math.max(max, r - l);}

问题在于：左指针可能重复经过同一字符多次。字符串"aaaaaa"会让左指针遍历5+4+3+2+1=15次，而非最优的6次。

解法二：数组预存的O(n)跳跃

核心洞察：字符出现过的位置可以直接"记住"，左指针无需试探，直接瞬移到重复位置之后。

int[] lastPos = new int[256];Arrays.fill(lastPos, -1);while (r < s.length()) {char c = s.charAt(r);if (lastPos[c] >= l) {      // 重复发生在当前窗口内l = lastPos[c] + 1;      // 左指针直接跳跃lastPos[c] = r;              // 更新最新位置max = Math.max(max, r - l + 1);r++;}

256长度的数组替代HashSet，索引访问O(1)；左指针从不回退，整体线性扫描。

关键差异：一个条件的判断顺序

解法二的精髓在第三行：if (lastPos[c] >= l)。若省略此判断，直接将l跳到lastPos[c] + 1，会错误地把窗口缩到历史重复点——即便该字符早已滑出窗口。

面试现场，写出解法一已算及格；但能否说出"数组比HashSet快在CPU缓存局部性"，能否把空间复杂度从O(min(m,n))压到O(1)（字符集大小固定），才是区分度的来源。

滑动窗口的模板人人会背，边界条件的毫厘之差，决定了代码是AC还是TLE。