哈希线四道:无重复字符的最长子串(3)、有效的括号(20)、LRU 缓存(146)、字符串解码(394)。前两道是哈希与栈的基本功,146 是本场压轴——它同时考哈希表、双向链表与数据结构设计,还是第 27.5 讲手写框架的算法版亲戚。这一讲以 3 为轴讲滑动窗口,以 146 为轴讲「设计题怎么答」。
哈希表是工程里用得最多的结构(第 6 章整章在讲它),面试官用算法题验证你会不会用它换时间。判断「存在吗」「上次出现在哪」「配对了吗」,第一反应是哈希而不是双重循环,就是及格线。滑动窗口则是「子串/子数组连续」类问题的标准解法,识别信号词就上套路。
滑动窗口(左右边界在数组上滑动的区间维护技巧)像卡着栅栏看风景:右边界扩张纳入新元素,左边界收缩排除旧元素,窗口内维护一个「当前状态」(如字符计数)。它的成立条件是单调性:左边界收缩后问题状态可以增量更新,不需要重算。栈(后进先出)则像叠盘子,天然的「最近匹配」结构——括号配对、括号嵌套解码都是它。
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last.containsKey(c)) // 出现重复:左界跳到
left = Math.max(left, // 重复字符上次位置的下一位
last.get(c) + 1);
last.put(c, right); // 记录最新位置
ans = Math.max(ans, right - left + 1);
}
return ans;
}
易错点:左界只能前进不能后退——Math.max 防止已被排除的旧位置把 left 拉回去。这一行是本题的区分度所在。
有效的括号(20):左括号入栈,右括号弹栈匹配,结束栈空则合法——三个细节:奇数长度直接 false、弹空前判空、右括号开头判 false。字符串解码(394):遇到 [ 把「当前字符串与倍数」压栈,遇到 ] 弹出拼接——双栈各自保存数字与字符串,嵌套天然正确。LRU 缓存(146):HashMap 定位 + 双向链表维护时序——get/put 命中后把节点摘下挂到头部,容量满时删尾部。手写要点:虚拟头尾两个哨兵让摘除与插入永远不用判空(与 32.2 的 dummy 一脉相承);先摘再插;删除 map 里的 key 别忘。面试的加分答法是提一句:JDK 的 LinkedHashMap(accessOrder=true) 加 removeEldestEntry 十行实现同款语义,但手写版才能展示链表操作(第 27.5 讲有完整手写复盘)。
146 的手写骨架(哨兵版,指针操作略):
class LRUCache {
static class Node { int k, v; Node p, n; }
Map<Integer, Node> map = new HashMap<>();
Node head = new Node(), tail = new Node(); // 虚拟头尾哨兵
int cap;
public int get(int key) {
Node x = map.get(key);
if (x == null) return -1;
unlink(x); addFirst(x); // 命中→摘下挂头
return x.v;
}
public void put(int key, int value) {
Node x = map.get(key);
if (x != null) { x.v = value; unlink(x); addFirst(x); return; }
if (map.size() == cap) { Node last = tail.p; unlink(last); map.remove(last.k); }
Node n = new Node(); n.k = key; n.v = value; addFirst(n); map.put(key, n);
}
}
设计题的答题结构比代码更值钱,四段走:选型理由(HashMap 提供 O(1) 定位,双向链表提供 O(1) 摘挂——单链表找不到前驱,这一句是灵魂)、复杂度承诺(get/put 均 O(1))、边界(容量一、空操作、key 已存在)、扩展(并发怎么办:分段锁思路或直接 ConcurrentHashMap+锁,正好回扣 6.2 的演进;淘汰策略变体:LFU 按频次、Redis 的近似 LRU 采样淘汰是 10.1 讲过的工程折衷)。滑动窗口的变体雷达也要装上:窗口内「最长」用右扩左缩求最大(3),「最短覆盖」反过来——右界扩张到满足,左界收缩到极限(76 最小覆盖子串,需要计数窗口);「长度最小子数组和」(209)是数值版同构。看到「子串/子数组+连续」,先判最大最小方向,再定窗口内维护什么状态——这是窗口题的两步审题法。
20 与 394 都是栈,但「栈里存什么」分了岔:20 存待匹配的左括号(字符级),394 存嵌套现场的快照(字符串与倍数两个栈)——存快照这个动作,本质是 32.5 回溯的「撤销选择」在字符串上的投影,两边可以互相印证着答。哈希侧还有一个高频追问值得备好:哈希冲突怎么办、什么时候退化——拉链法与开放寻址(第 6.1 讲拆过 HashMap),负载因子超阈值扩容重分布;工程里因此有「别拿哈希当有序结构用」的铁律。再往算法题延伸一格:布隆过滤器(位数组+k 个哈希函数的概率型判重结构)是「缓存穿透」的标准防线(第 10.4 讲的三兄弟之一),它的「可能存在/一定不存在」不对称判断也是一道独立的面试题——从一道滑动窗口题出发,把考点牵到工程纵深,是这一讲最划算的答法。
把滑动窗口固化成三问:一问方向——求最长(窗口越滑越大,记录过程最大值)还是求最短(滑到满足后收缩,记录过程最小值);二问状态——窗口内维护什么(字符计数、去重集合、数值和),状态必须能增量更新,若不能(如需要排序的窗口),降级为滑动窗口+有序结构或回溯;三问边界——左界能不能跳(3 题跳到重复位+1,76 题只能一步一步缩)。三问答完,代码骨架已经出来:一个 for 推右界、一个 while 收左界、窗口状态进出各一行、答案比较一行——五行骨架对所有窗口题通用,变量名都一样,这就是「模板级熟练」的样子。
哈希换时间、栈管匹配、滑动窗口管连续区间、双向链表管时序——四道题四个结构,LRU 把它们串成一道设计题,正是第 27.5 讲手写传统的延续。