Leetcode热题100_3.无重复字符的最长子串

题目要求

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

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。

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

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

滑动窗口

滑动窗口其实就是一个队列,比如例题中的abcabcbb，进入这个队列（窗口）为abc满足题目要求，当再进入a，队列变成了abca，这时候不满足要求。所以，我们要移动这个队列

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求。

一直维持这样的队列，找出队列出现最长的长度时候，求出解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;

        // 哈希表记录字符上一次出现的位置
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        
        int maxLen = 0;
        for (right = 0; right < s.length(); right++) {
            // 如果当前字符之前出现过，则更新左边界
            if (map.containsKey(s.charAt(right))) {
                // 更新左边界为上一次出现位置的下一个位置，确保窗口内没有重复字符
                left = Math.max(left, map.get(s.charAt(right)) + 1);
            } 
            map.put(s.charAt(right), right);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}
  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符被访问两次（一次右指针移动，一次左指针移动），因此总时间复杂度为 O(n)。
  • 空间复杂度：O(min(m, n))，其中 m 是字符集的大小，n 是字符串 s 的长度。哈希表中存储的字符数量不会超过字符集的大小或字符串的长度。