今天看到一个非常牛逼的算法, 激动得睡不着觉, 趁着脑子还有余热能理解过程, 赶紧写下来.
原题
链接: https://leetcode.cn/problems/longest-substring-without-repeating-characters/
算法
初见题目相信很多人都想到了滑动窗口解法, 然而下面的算法更为精妙
public int lengthOfLongestSubstring(String s) {
int[] index = new int[128];
int ans = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
j = Math.max(index[s.charAt(i)], j);
ans = Math.max(i - j + 1, ans);
index[s.charAt(i)] = i + 1;
}
return ans;
}
仅仅不到 10 行的核心代码, 执行效率超过 100% , 内存利用率也超过将近 90% 的提交!
解析
先来点注释, 简单点明下每步的含义
注: 次序, 即索引+1 的值, 表示出现在第几次, 次序 1 表示第一次, 次序 2 表示第二次, 以此类推, 与索引道理相同. 引入次序的概念在 debug 看原理时会清晰不少
public int lengthOfLongestSubstring(String s) {
int[] index = new int[128]; // ASCII 占位表又来了
int ans = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
// 2. j 记录不重复字符的最大起点的次序
j = Math.max(index[s.charAt(i)], j);
// 3. i + 1 是当前字符出现的次序, 与上述 j 相减就是这次循环中不重复字符的最大间隔
ans = Math.max(i + 1 - j, ans);
// 1. 把当前字符的本次出现的次序记录到占位表中
index[s.charAt(i)] = i + 1;
}
return ans;
}
思考记录
为了方便表示, s 的第 i 个字符姑且记为 s[i]
- 此算法的核心在于利用 ASCII 码表记录每一个字符的最后出现次序
- 循环中的三句代码的逻辑顺序其实是 2, 3, 1, 已在注释中标明
- j 有两个含义
- 当
index[s.charAt(i)]比较大时, 表示了迄今为止 s[i] 最后一次出现的次序(串中的第几个字符, 即索引+1), 0 表示之前没有出现过(巧妙利用了数组初始值为 0 的特性) - 当上个循环的
j比较大时, 表示的是之前出现过的连续重复字符的倒数第二个字符的次序, 即若 aab 字符串, 当前循环到 b , 表达式的 j 表示第一个 a 的次序 - 这两者的共同含义就是不重复字符的最大起点次序
- 当
- ans 就是最大不重复子串的长度
-
index[s.charAt(i)] = i + 1最后一步是将当前字符出现次序更新到占位表, 以供下个循环的 j 使用
语言表达的内容是非常有限的, 要真正搞懂一定要动手单步调试
