LeetCode-3 无重复字符的最长子串

> 题目：3. 无重复字符的最长子串

> 难度：中等

> 分类：字符串

> 解决方案：双指针、滑动窗口

LeetCode前几道题都是经典题，今天我们学习第3题无重复字符的最长子串，这道题在秋招面试中遇见过，再次相遇，如此亲切。下面我们看看这道题的题目描述。

题目描述

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

示例1：

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

示例2：

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

示例3：

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

分析

首先我们看看这个题的示例3，该示例中提示我们这个题求字符串的子串而不是子序列，我们具体来看看什么是子串，什么是子序列。

子串：字符串中任意个连续的字符组成的子序列称为该串的子串。注意子串强调字符的连续性。如图1所示。 子序列：字符串中去掉任意个元素后得到的结果即为该字符串的子序列。注意子序列中字符出现的次序与原字符串中字符出现的次序要保持一致。如图2所示。

[图1. 子串]

[图2. 子序列]

区分子串和子序列后，我们再回过头来看看这个题。我们先动手画一画示例1的解题过程，如图3所示：

[图3. 示例1分析过程图解]

从上图我们可以观察出，可以使用双指针（ left指针和 right指针）来维护一个滑动窗口，这个窗口内的字符都是没有重复的，遍历一趟字符串后就可以得到最大的子串，因此时间复杂度为 O(n)。现在想一个问题：right指针指向的字符怎么确定它在前面是否出现过，若出现过，它出现的位置在哪儿？对于这个问题，做过LeetCode-1 两数之和这道题的小伙伴们应该知道，我们可以使用 HashMap记录一个字符是否出现以及出现后的位置。对于重复多次出现的字符，我们是保留所有出现的位置还是只记录一个位置？观察示例1分析过程可以知道，我们只需要保存一个最大位置即可。还有一个关键点，我们如何确定 left指针的位置？这一点非常重要，需要分情况讨论。

• 当目前 right指针指向的字符未出现过， left指针不需要移动；
• 当目前 right指针指向的字符出现过，如果该字符在窗口中，即该字符出现在当前 left指针的右边，则通过 HashMap获取字符的位置并向右移动一位即为更新后 left的位置；如果该字符在窗口外面，即在当前 left指针的左边，则不需要移动 left的位置。

分析完后，再看看 java代码的具体实现：

class Solution {    public int lengthOfLongestSubstring(String s) {        int res = 0;        if(s.length() == 0)            return res;        // 创建HashMap，用来保存字符与位置之间的对应关系        HashMap<Character, Integer> hashMap = new HashMap<>();        // 初始化左指针和右指针，并遍历字符串        for(int left = 0, right = 0; right < s.length(); right++){            // 判断右指针指向的字符是否出现过            if(hashMap.containsKey(s.charAt(right))){                // 确定左指针的位置                left = Math.max(left, hashMap.get(s.charAt(right))+1);            }            // 对于第一次出现的字符，保存该字符的位置；对于多次出现的字符，更新该字符出现的位置            hashMap.put(s.charAt(right), right);            // 更新窗口的大小，保存最大的窗口大小            res = Math.max(res, right-left+1);        }        return res;    }}

整个算法流程的时间复杂度为 O(n)，空间复杂度为 O(1)。

Github地址

LeetCode-3 无重复字符的最长子串：https://github.com/JacobLei/leetcode/blob/master/src/main/java/A3_LongestSubstringWithoutRepeatingCharacters.java

参考链接

无重复字符的最长子串：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/