LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 利用滑动窗口来依次匹配，窗口左右边界为 l 和 r，窗口包含 左右边界，l 和 r 均初始化为 0
• 窗口不满足条件时（即 s[l]...s[r] 未包含 t 的所有字符），不断右移 r，直到窗口满足条件
• 窗口满足条件时，不断右移 l，直到窗口不满足条件
• 重复上述两步，直到 r 超出 s 右边界。整个过程中，满足条件且长度最短的窗口即为返回值

ADOBECODEBANC => 不包含 ABC，右移 r
↑
l
r

ADOBECODEBANC => 包含 ABC，右移 l
↑    ↑
l    r

ADOBECODEBANC => 不包含 ABC，右移 r
 ↑   ↑
 l   r

ADOBECODEBANC => 包含 ABC，右移 l
 ↑        ↑
 l        r

ADOBECODEBANC => 包含 ABC，右移 l
  ↑       ↑
  l       r

ADOBECODEBANC => 包含 ABC，右移 l
   ↑      ↑
   l      r

ADOBECODEBANC => 包含 ABC，右移 l
    ↑     ↑
    l     r

ADOBECODEBANC => 包含 ABC，右移 l
     ↑    ↑
     l    r


ADOBECODEBANC => 不包含 ABC，右移 r
      ↑   ↑
      l   r

ADOBECODEBANC => 包含 ABC，右移 l
      ↑     ↑
      l     r

ADOBECODEBANC => 包含 ABC，右移 l
         ↑  ↑
         l  r

ADOBECODEBANC => 不包含 ABC，右移 r，超出边界，结束
          ↑ ↑
          l r

整个过程中满足条件的最短子串 BANC 即为结果

• 解法如下

class Solution {
 public:
  string minWindow(string s, string t) {
    unordered_map<char, int> m;
    for (auto& x : t) {
      ++m[x];  // 记录 t 中所有字符的出现次数
    }
    int minLen = INT_MAX;  // 最小窗口长度
    int start = 0;         // 窗口长度最小时的起点
    int l = 0;
    int cnt = 0;  // 窗口包含的目标字符数
    for (int r = 0; r < size(s); ++r) {
      if (--m[s[r]] >= 0) {
        ++cnt;
      }
      while (cnt == size(t)) {  // 窗口满足条件
        if (r - l + 1 < minLen) {
          minLen = r - l + 1;
          start = l;
        }
        if (++m[s[l]] > 0) {
          --cnt;
        }
        ++l;
      }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
  }
};