leetcode：3. 无重复字符的最长子串

题目

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

示例：

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

解答 & 代码

滑动窗口：（不过本题不能再直接套滑动窗口的框架了）

  1. class Solution {
  2. public:
  3.     int lengthOfLongestSubstring(string s) {
  4.         // 哈希表，记录窗口中出现的字符及下标，key=字符, val=下标
  5.         unordered_map<char, int> window;
  6.         int left = 0;
  7.         int right = 0;
  8.         int maxLen = 0;
  9.         // 滑动窗口 [left, right)
  10.         while(right < s.size())
  11.         {
  12.             char ch = s[right];        // 将要添加到窗口的字符
  13.             ++right;                // 右指针右移，窗口扩增
  15.             // 如果该字符不在窗口中，则将<该字符，下标>加入窗口的哈希表
  16.             // 判断窗口在哈希表中有两种可能性：
  17.             // a. 哈希表中不存在该字符； b. 该字符对应的下标小于左边界
  18.             if(window.find(ch) == window.end() || window[ch] < left)
  19.                 window[ch] = right - 1;
  20.             // 如果该字符在窗口中已经存在，则：
  21.             else
  22.             {
  23.                 // 用当前窗口长度 -1 （去掉最后这个重复字符）和最长子串长度比较，更新最长子串长度
  24.                 maxLen = max(maxLen, right - left - 1);
  25.                 // 左指针右移，直接跳到该字符上一次出现的位置之后，使得窗口内无重复字符
  26.                 left = window[ch] + 1;
  27.                 // 更新哈希表中这个重复字符的下标
  28.                 window[ch] = right - 1;
  29.             }
  30.         }
  31.         // 最后还要再更新一下 maxLen
  32.         // 否则 eg. 字符串" "就错误地输出 0，实际应为 1 
  33.         maxLen = max(maxLen, right - left);
  34.         return maxLen;
  35.     }
  36. };

复杂度分析：设字符串 s 长为 N，包含 C 个不同的字符

  • 时间复杂度 O(N)：最坏情况下，字符串 s 的每个字符分别被左、右指针遍历一次
  • 空间复杂度 O(C)：最坏情况下，哈希表占的空间 = 字符串s 中不同字符的种数 C

执行结果：

  1. 执行结果：通过
  3. 执行用时：8 ms, 在所有 C++ 提交中击败了 86.49% 的用户
  4. 内存消耗：8.1 MB, 在所有 C++ 提交中击败了67.61% 的用户