题目链接

3. Longest Substring Without Repeating Characters

题目描述

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

示例：

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

解题思路

[a]bcabcbb        子串长度为1
[ab]cabcbb        子串长度为2
[abc]abcbb        子串长度为3

此时的窗口大小为3，继续添加字符时会出现重复字符，此时移动窗口。

a[bca]bcbb        子串长度为3
ab[cab]cbb        子串长度为3
abc[abc]bb        子串长度为3
abcab[cb]b        子串长度为2
abcabcb[b]        子串长度为1

最终记录的无重复字符的最长子串长度为3

1. 利用 HashSet 作为滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 记录无重复子串的最大长度
        int maxLen = 0;
        // 滑动窗口的左右边界
        int left = 0;
        int right = 0;
        HashSet<Character> set = new HashSet<>();
        while (right < s.length()) {
            // 如果当前遍历到的字符已经在窗口中，说明重复
            // 将在左边出现的重复字符及其前面的字符全部删除（也就找到重复字符的下一个字符）
            while (set.contains(s.charAt(right))) {
                /*
                    这里可以优化的点，当发现了一个已经重复的字符，
                    窗口的左边界移动到左边的那个重复字符的下一个字符开始即可，而不需要遍历删除

                    比如：abcbad
                        当遍历到第 2 个 b 时，
                        左边界直接设置到左边的那个重复字符的下一个字符 c 所在下标即可。
                 */
                set.remove(s.charAt(left++));
            }
            // 添加到窗口中
            set.add(s.charAt(right++));
            // 记录最大长度
            maxLen = Math.max(maxLen, set.size());
        }
        return maxLen;
    }
}

• 时间复杂度：。
• 空间复杂度：，N 取决于字符串的字符集大小。

  2. 使用 HashMap 优化

对于字符串pwwkew，当right指针遍历到第二个 w 时，出现了重复字符，此时统计一次子串长度。

如果使用HashSet，那么会将left指针到第一个 w 处，继续寻找下一个子串。但是我们可以发现，此时以第一个 w 为起始字符所形成的「不包含重复字符」的子串的长度是一定小于以 p 为起始字符所形成的「不包含重复字符」的子串长度。因为两者的结束位置相同，但是 p 的起始位置大于第一个 w 的起始位置。

也就是说，我们当我们寻找下一个「不包含重复字符」的子串时，可以直接以第一个重复字符的下一个字符为起始位置。比如对于上面这个例子，当遍历到第二个 w 时出现了重复，此时寻找下一个子串时就可以直接从第一个 w 的下一个字符作为起始字符。

算法流程：

• 判断当前字符s.charAt(right)是否包含在HashMap中。
  • 如果不包含，则将该字符添加到哈希表中，统计此时以 left 为起始字符的无重复字符子串的长度ans。
  • 如果包含，此时应该移动left指针到第一个重复字符的下一个位置，这包含两种情况：
    1. 对于字符串'abca'，当遍历到第二个 a 时，left 应更新为第一个 a 的下一个位置，即：left = map.get(a) + 1 = 1。
    2. 对于字符串'abba'，当遍历到第二个 b 时，left 应更新为第一个 b 的下一个位置，即：left = map.get(b) + 1 = 2。继续移动right指针，当遍历到第二个 a 时，left 应该更新为第一个 a 的下一个位置，但是此时left将回到第一个 b 的位置，即left = map.get(a) + 1 = 1。如果按left = 1来统计当前子串，可得子串为bba，很明显不符合条件。而left为 2 时，得到子串ba是符合条件的。
    • 为了处理第二种情况，必须将 left 更新为更大的那一个，所以代码为left = Math.max(left, map.get(s.charAt(right)) + 1)。

• 返回「无重复字符的最长子串」的长度。

  class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int ans = 0;
        while (right < s.length()) {
            if (map.containsKey(s.charAt(right))) {
                // 注意！注意！注意！
                left = Math.max(left, map.get(s.charAt(right)) + 1);
            }
            map.put(s.charAt(right), right);
            ans = Math.max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
  }
  

• 时间复杂度：。相较于使用HashSet，会节省一些常数时间。

• 空间复杂度：。N 取决于字符串的字符集大小。