3. 滑动窗口

3.1 无重复字符的最长子串

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

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

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

   示例 2：

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

   示例 3：

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

   提示

   思路：典型的不定长滑动窗口思想。入——出——更新。用一个计数器来记录窗口内每种元素的个数，如果遇到重复元素，则收缩窗口。

   Python

   class Solution:
   def lengthOfLongestSubstring(self, s: str) -> int:
   
       from collections import Counter
       cnt = Counter()
       left = 0
       res = 0
       for right, c in enumerate(s):
           cnt[c] += 1
           while cnt[c] > 1:
               cnt[s[left]] -= 1
               left += 1
           res = max(res, right - left + 1)
       return res

   C++

   class Solution {
   public:
       int lengthOfLongestSubstring(string s) {
           unordered_map<char, int> cnt;
           int left = 0, res = 0;
           for (int right = 0; right < s.length(); right++) {
               char c = s[right];
               cnt[c]++;
               while (cnt[c] > 1) {
                   cnt[s[left]]--;
                   left++;
               }
               res = max(res, right - left + 1);
           }
           return res;
       }
   };

   时间复杂度：$O(n)$。

   空间复杂度：$O(n)$。

3.2 找到字符串中所有字母异位词

2. 438. 找到字符串中所有字母异位词

   给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
   示例 1：

   输入: s = "cbaebabacd", p = "abc"
   输出: [0,6]
   解释:
   起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
   起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

   示例 2：

   输入: s = "abab", p = "ab"
   输出: [0,1,2]
   解释:
   起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
   起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
   起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

   提示

   思路：滑动窗口思想。

   重要

   定长滑动窗口思想。维护长度为 len(p) 的定长滑动窗口，如果当前窗口匹配上指定窗口，则加入左端点下标。无论是否匹配，都要丢弃左端元素进入下一轮匹配。为了使用 == 判断两个计数器是否等价，要记得删除数量为 0 的 key。

   Python

   class Solution:
   def findAnagrams(self, s: str, p: str) -> List[int]:
       cnt_p = Counter(p)
       cnt_s = Counter()
       res = []
       for right, c in enumerate(s):
           cnt_s[c] += 1
           left = right - len(p) + 1
           if left < 0:
               continue
           if cnt_s == cnt_p:
               res.append(left)
           cnt_s[s[left]] -= 1
           if cnt_s[s[left]] == 0:
               del cnt_s[s[left]]
       return res

   C++

   class Solution { // 辅助空间用数组做法
   public:
       vector<int> findAnagrams(string s, string p) {
           array<int, 26> cnt_s{};
           array<int, 26> cnt_p{};
           vector<int> res;
           for (char c : p) {
               cnt_p[c - 'a']++;
           }
           for (int right = 0; right < s.length(); right++) {
               cnt_s[s[right] - 'a'] += 1;
               int left = right - p.length() + 1;
               if (left < 0) continue;
               if (cnt_p == cnt_s) {
                   res.push_back(left);
               }
               cnt_s[s[left] - 'a'] -= 1;
           }
           return res;
       }
   };

   C++

   class Solution { // 辅助空间用哈希表做法
   public:
       vector<int> findAnagrams(string s, string p) {
           unordered_map<char, int> cnt_s;
           unordered_map<char, int> cnt_p;
           vector<int> res;
           for (char c : p) {
               cnt_p[c]++;
           }
           for (int right = 0; right < s.length(); right++) {
               cnt_s[s[right]] += 1;
               int left = right - p.length() + 1;
               if (left < 0) continue;
               if (cnt_p == cnt_s) {
                   res.push_back(left);
               }
               if (--cnt_s[s[left]] == 0) {
                   cnt_s.erase(s[left]);
               }
           }
           return res;
       }
   };

   时间复杂度：$O(∣Σ∣m+n)$，其中 m 是 s 的长度，n 是 p 的长度，∣Σ∣=26 是字符集合的大小。

   空间复杂度：$O(∣Σ∣)$。返回值不计入。

   重要

   不定长滑动窗口思想。只使用一个计数器cnt统计p的字符，每遍历一个s中的元素就减少cnt的数量，如果减少当前元素数量后计数器没有负数且长度也相等，那么就匹配成功。

   Python

   class Solution:
   def findAnagrams(self, s: str, p: str) -> List[int]:
       cnt = Counter(p)
       left = 0
       res = []
       for right, c in enumerate(s):
           cnt[c] -= 1
           while cnt[c] < 0:
               cnt[s[left]] += 1
               left += 1
           if right - left + 1 == len(p):
               res.append(left)
       return res

   C++

   class Solution {
   public:
       vector<int> findAnagrams(string s, string p) {
           int cnt[26] = {0};
           vector<int> res;
           int left = 0;
           for (char c : p) {
               cnt[c - 'a']++;
           }
           for (int right = 0; right < s.length(); right++) {
               cnt[s[right] - 'a']--;
               while (cnt[s[right] - 'a'] < 0) {
                   cnt[s[left] - 'a']++;
                   left++;
               }
               if (right - left + 1 == p.length()) res.push_back(left);
           }
           return res;
       }
   };

   时间复杂度：$O(m+n)$，其中 m 是 s 的长度，n 是 p 的长度。虽然写了个二重循环，但是内层循环中对 left 加一的总执行次数不会超过 m 次，所以滑窗的时间复杂度为 $O(m)$。

   空间复杂度：$O(∣Σ∣)$，其中 ∣Σ∣=26 是字符集合的大小。返回值不计入。

帮助我修改错误

贡献者: zzyAJohn

上一页2. 双指针

下一页4. 子串