leetcode 面试经典 150 题：无重复字符的最长子串

题目

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

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

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

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

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

解题

1. 核心要点：这个问题可以通过滑动窗口的方法来解决。滑动窗口表示当前考虑的子串的范围，我们通过移动窗口的边界来找到不含有重复字符的最长子串。

   • 初始化：定义两个指针 left 和 right 分别表示窗口的左右边界，以及一个哈希表 char_index_map 来存储字符及其索引。
   • 扩展窗口：将 right 指针向右移动，扩展窗口，直到遇到重复的字符。
   • 更新最大长度：在每次移动 right 指针时，更新不含有重复字符的子串的最大长度。
   • 收缩窗口：当遇到重复的字符时，移动 left 指针，收缩窗口，直到重复的字符被移出窗口。
   • 重复步骤2-4：直到 right 指针到达字符串的末尾。

2. 时间复杂度： O(n)

3. 空间复杂度：O(n)

4. c++ 实现算法：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        unordered_map<char, int> map; // 哈希表记录字符的最新索引，map 的键是字符，值是该字符的最后出现的索引位置
        int max_len = 0; // 最长子串长度
        int left = 0; // 滑动窗口的左边界

        for (int right = 0; right < s.size(); ++right) {

            // 如果当前字符在窗口内出现过，更新窗口的左边界
            //如果 map.find(s[right]) 返回的不是 map.end()，意味着哈希表中存在字符 s[right]，
            //也就是说，字符 s[right] 在哈希表中出现过。
            
            //如果返回 map.end()，则说明哈希表中没有这个字符，即字符 s[right] 没有在哈希表中出现过。
            //map[s[right]] >= left，字符 s[right] 在窗口中的 上一次出现的位置 
            //大于等于当前窗口的左边界 left，那么就说明它是重复的。
            if (map.find(s[right]) != map.end() && map[s[right]] >= left) {
                //将 left 更新为字符 s[right] 最新出现位置的下一个位置
                left = map[s[right]] + 1;
            }
            
            // 更新当前字符的最新位置
            map[s[right]] = right;
            
            // 计算当前窗口的大小，更新最大长度
            max_len = max(max_len, right - left + 1);
        }

        return max_len;
    }
};

5. 演示：以示例1为例

遍历字符串 s，right 从 0 到 7：

1. right = 0，字符 ‘a’： map.find(s[right]) != map.end() 检查字符 ‘a’ 是否已经出现过。由于 map 为空，所以字符 ‘a’ 不在其中。 更新哈希表：map[‘a’] = 0。字符 ‘a’ 的最新索引是 0。计算当前窗口大小：right - left + 1 = 0 - 0 + 1 = 1。 更新 max_len：max_len = max(0,1) = 1。

2. right = 1，字符 ‘b’： map.find(s[right]) != map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 不在哈希表中。 更新哈希表：map[‘b’] = 1。字符 ‘b’ 的最新索引是 1。计算当前窗口大小：right - left + 1 = 1 - 0 + 1 = 2。 更新 max_len：max_len = max(1, 2) = 2。

3. right = 2，字符 ‘c’： map.find(s[right]) != map.end() 检查字符 ‘c’ 是否已经出现过。字符 ‘c’ 不在哈希表中。 更新哈希表：map[‘c’] = 2。字符 ‘c’ 的最新索引是 2。计算当前窗口大小：right - left + 1 = 2 - 0 + 1 = 3。 更新 max_len：max_len = max(2, 3) = 3。

4. right = 3，字符 ‘a’： map.find(s[right]) != map.end() 检查字符 ‘a’ 是否已经出现过。字符 ‘a’ 已经在 map 中，且它的索引是 0（小于 right = 3）。 由于 ‘a’ 重复了，我们需要更新滑动窗口的左边界： left = map[‘a’] + 1 = 0 + 1 = 1，新的左边界是 1，即跳过 a 在左边的位置。 更新哈希表：map[‘a’] = 3。字符 ‘a’ 的最新索引是 3。 计算当前窗口大小：right - left + 1 = 3 - 1 + 1 = 3。 max_len 仍然是 3（不更新）。

5. right = 4，字符 ‘b’： map.find(s[right]) != map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 已经在 map 中，且它的索引是 1（小于 right = 4）。 由于 ‘b’ 重复了，我们需要更新滑动窗口的左边界： left = map[‘b’] + 1 = 1 + 1 = 2，新的左边界是 2，即跳过 b 在左边的位置。 更新哈希表：map[‘b’] = 4。字符 ‘b’ 的最新索引是 4。 计算当前窗口大小：right - left + 1 = 4 - 2 + 1 = 3。 max_len 仍然是 3（不更新）。

6. right = 5，字符 ‘c’： map.find(s[right]) != map.end() 检查字符 ‘c’ 是否已经出现过。字符 ‘c’ 已经在 map 中，且它的索引是 2（小于 right = 5）。 由于 ‘c’ 重复了，我们需要更新滑动窗口的左边界： left = map[‘c’] + 1 = 2 + 1 = 3，新的左边界是 3，即跳过 c 在左边的位置。 更新哈希表：map[‘c’] = 5。字符 ‘c’ 的最新索引是 5。 计算当前窗口大小：right - left + 1 = 5 - 3 + 1 = 3。 max_len 仍然是 3（不更新）。

7. right = 6，字符 ‘b’： map.find(s[right]) != map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 已经在 map 中，且它的索引是 4（小于 right = 6）。 由于 ‘b’ 重复了，我们需要更新滑动窗口的左边界： left = map[‘b’] + 1 = 4 + 1 = 5，新的左边界是 5，即跳过 b在左边的位置。 更新哈希表：map[‘b’] = 6。字符 ‘b’ 的最新索引是 6。 计算当前窗口大小：right - left + 1 = 6 - 5 + 1 = 2。 max_len 仍然是 3（不更新）。

8. right = 7，字符 ‘b’： map.find(s[right]) != map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 已经在 map 中，且它的索引是 6（小于 right = 7）。 由于 'b’重复了，我们需要更新滑动窗口的左边界： left = map[‘b’] + 1 = 6 + 1 = 7，新的左边界是 7，即跳过 b 在左边的位置。 更新哈希表：map[‘b’] = 7。字符 ‘b’ 的最新索引是 7。 计算当前窗口大小：right - left + 1 = 7 - 7 + 1 = 1。 max_len 仍然是 3（不更新）。

6. c++ demo：

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        unordered_map<char, int> map; // 哈希表记录字符的最新索引，map 的键是字符，值是该字符的最后出现的索引位置
        int max_len = 0; // 最长子串长度
        int left = 0; // 滑动窗口的左边界

        for (int right = 0; right < s.size(); ++right) {

            // 如果当前字符在窗口内出现过，更新窗口的左边界
            //如果 map.find(s[right]) 返回的不是 map.end()，意味着哈希表中存在字符 s[right]，
            //也就是说，字符 s[right] 在哈希表中出现过。
            
            //如果返回 map.end()，则说明哈希表中没有这个字符，即字符 s[right] 没有在哈希表中出现过。
            //map[s[right]] >= left，字符 s[right] 在窗口中的 上一次出现的位置 
            //大于等于当前窗口的左边界 left，那么就说明它是重复的。
            if (map.find(s[right]) != map.end() && map[s[right]] >= left) {
                //将 left 更新为字符 s[right] 最新出现位置的下一个位置
                left = map[s[right]] + 1;
            }
            
            // 更新当前字符的最新位置
            map[s[right]] = right;
            
            // 计算当前窗口的大小，更新最大长度
            max_len = max(max_len, right - left + 1);
        }

        return max_len;
    }
};

int main() {
    Solution sol;
    string s = "abcabcbb";
    cout << "The length of the longest substring without repeating characters is: " 
         << sol.lengthOfLongestSubstring(s) << endl;
    return 0;
}