第1.8篇·无重复字符的最长子串

算法是求职的敲门砖，大厂面试一面几乎都会问算法题，以此来考察候选人的思维逻辑及编码能力。

今天要AC的题目叫做「无重复字符的最长子串」，在 leetcode 上的原题链接为：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

1. 题目

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1：

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2：

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

• 提示：
  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

2. 解题思路

这道题目还是比较容易理解的，给出一个字符串，要求输出没有重复字符的最长子串长度。乍一看好像挺简单的，一次循环，每次找到当前字符串的下一个字符位置，然后求差即可。

第一次我就是这么做的，然而在调试的时候突然想到一个用例——“abcbd”，理论上它的输出结果应该是3，cbd 是它的不重复最长子串。但是我的代码输出的却是5，这就让我想到，我不应该只考虑子串第一个元素是否重复，它的每一个元素我都应该考虑是否重复。

基于此，我才用滑动窗口的解法，定义两个变量 left 和 right 用来表示最长子串的左元素坐标和右元素坐标，然后使用一个 HashMap 来存储每一个元素的最新坐标，这里为什么说是最新坐标呢？因为 HashMap 是一个不包含重复元素的容器，如果 key 相同，则 value 会更新。

对输入的字符串进行遍历，判断当前字符串是否已存在于 Map，如果存在了，left 需要变更为当前字符串在 map 中的下标位置后移一位（这是因为需要排除当前字符串这个重复元素）。然后向 Map 中设置当前字符的最新坐标，最后在本次循环结束前，判断一下当前子串的长度是否是最长的。

我们以示例3「pwwkew」为例用图来解释一下滑动窗口的解法。

声明 left 为滑动窗口的左下标，right 为滑动窗口的右下标，max 表示滑动窗口的长度，map 存储每个字符的最新节点，各变量初始状态如下：

第一次循环开始，首先判断字符是否已存在，结果当然是不存在，所以不需要变动滑动窗口起始下标 left 的值，然后在 map 中记录当前字符的位置，最后计算本次循环结束后当前滑动窗口的的长度，第一次循环结束后各变量状态如下：

同理，第二次循环结束后各变量状态如下：

第三次循环开始，这与前两次有些不同，因为 w 字符是已存在过的字符，所以需要将滑动窗口起始下标 left 变更为当前字符串在 Map 中的下标位置再右移一位，然后更新此字符串坐标值，最后计算窗口长度，与最大值进行比较，第三次循环结束后各变量状态如下：

同理，第四次循环结束后各变量状态如下：

第五次循环结束后各变量状态如下：

第六次循环结束后各变量状态如下：

最终，输出滑动窗口的最大长度3即为输出结果。

用 Java 实现上述思路的代码是：

上述示例代码在 leetcode 上的执行结果是：

最后，本文收录于个人语雀知识库: 我所理解的后端技术，欢迎来访。