每日LeetCode_230902

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

（1）题目

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

示例 1:

1
2
3

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

示例 2:

1
2
3

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

示例 3:

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

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

（2）题解

暴力循环

两层循环，外层循环从左侧开始，依次移动；内层循环从外层循环的下一个位置开始移动，每移动一次检测是否有重复，若有重复，则找到当前起始位置的最长子串，停止内层循环。

// 哈希表，用于检测是否有重复字符
unordered_set<char> HashTable;
// 最长子串长度
int maxlength = 0;       
int n = s.size();
// 外层循环从左向右遍历
for(int i =0; i<n; ++i){
  HashTable.insert(s[i]);
  // 内层循环从 i + 1 开始向右遍历
  for(int j = i + 1; j <= n; ++j){
    // 如果 j 到达边界，或者出现重复字符
    if(j == n || HashTable.find(s[j]) != HashTable.end()){
      // 更新最长子串长度
      maxlength = max(maxlength, j - i);
      break;
    }
    // 否则，将 s[j] 加入哈希表
    else{
      HashTable.insert(s[j]);
    }
  }
  // 清空哈希表
  HashTable.clear()
}
return maxlength;

该方法在每次外层循环时都要重建哈希表，对于内存的占用过高；同时，因为有两层循环，且每次都是逐个字母检测，耗时过长，并不推荐使用。

滑动窗口

假设我们选择字符串中的第 k 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 rk 。那么当我们选择第 k+1 个字符作为起始位置时，首先从 k+1 到 rk 的字符显然是不重复的，并且由于少了原本的第 k 个字符，可以尝试继续增大 rk ，直到右侧出现了重复字符为止。

使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表「枚举子串的起始位置」，右指针代表窗口的结束位置 rk ；
在每一步的操作中，将左指针向右移动一格，表示开始枚举下一个字符作为起始位置，然后不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着以左指针开始的，不包含重复字符的最长子串；
判断重复字符：哈希表（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）。在左指针向右移动的时候，从哈希集合中移除一个字符，在右指针向右移动的时候，往哈希集合中添加一个字符。
注意：这里所使用的哈希表只是为了确认每次加入的新字母是否与已有序列重复，因此加入后，统计表中的新字母的个数即可。

class Solution{
public:
    int lengthOfLongestSubstring(string s){
      // 哈希集合，记录每个字符是否出现过
      unordered_set<char> occ;
      int n = s.size();
      // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
      int rk = -1, ans = 0;
      // 枚举左指针的位置，初始值隐性地表示为 -1
      for (int i = 0; i < n; ++i){
        if (i != 0){
          // 左指针向右移动一格，移除一个字符
          occ.erase(s[i - 1]);
        }
        while (rk + 1 < n && !occ.count(s[rk + 1])){
          // 不断地移动右指针
          occ.insert(s[rk + 1]);
          ++rk;
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i + 1);
      }
      return ans;
    }
};

进一步改进，出现重复字符就缩小窗口

外层循环改进为右指针到达字符串末尾就停止循环，这样可以减少一定的循环次数；

循环内，仅用了 c 和 d 两个临时变量用于存储窗口的边界字符，并利用此检测是否有重复字符以及增减出现次数。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0; // 记录最长集合
        int left = 0; // 窗口左指针
        int right = 0; // 窗口右指针
        // 哈希表，记录每个字符是否出现过
        unordered_map<char, int> window;
        // 外层循环，扩张窗口
        while (right < s.size()) {
            char c = s[right]; // 记录右指针字符
            right++;
            window[c]++; // 将 c 在哈希表中出现的次数+1
            // 如果出现重复字符，就缩小窗口
            while (window[c] > 1) {
                char d = s[left]; // 记录左指针字符
                left++;
                window[d]--; // 减少 d 的出现次数
            }
            // 更新最长集合
            res = max(res, right - left);
        }
        return res;        
    }
};

window[c]++ 这一句代码的意思是将字符 c 在 window 映射中的出现次数加 1。如果 c 在 window 映射中不存在，则会自动插入一个键值对 (c, 0)，然后将出现次数加 1。这个操作可以用来维护当前窗口中每个字符的出现次数。

（3）知识点

滑动窗口算法：该算法是一种常用的解决字符串子串问题的方法。它通过维护一个窗口，来遍历字符串中的所有子串。在每次移动窗口时，可以通过一些技巧来避免重复计算，从而达到线性时间复杂度的目的。
哈希表：哈希表是一种常用的数据结构，可以用来快速地查找和插入元素。在本题中，我们可以使用哈希表来维护当前窗口中每个字符的出现次数。
双指针：双指针是一种常用的技巧，可以使用两个指针 i 和 j 来维护当前窗口的左右边界。