今天看到一个非常牛逼的算法, 激动得睡不着觉, 趁着脑子还有余热能理解过程, 赶紧写下来.

原题

链接: 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 使用

语言表达的内容是非常有限的, 要真正搞懂一定要动手单步调试