Example

双指针——滑动窗口 - 图1 （该串包含目标串的一个全排列，可以出现其它字符, ）

暴力

思路：

  • 把所有字符串扫描一次。
  • 判断是否包含所有字符， 是则记录信息。
  • 扫描完所有字符串，比较所有记录， 最短那个就是最小子串。

伪代码 

  1. for i in range(0, len(S)):
  2.     for j in range(1, len(S)):
  3.         if S[i:j] contain T:
  4.             记录i,j

时间复杂度：双指针——滑动窗口 - 图2

分析


双指针——滑动窗口 - 图3

  1. for i in range(0, len(S)):
  2.     for j in range(1, len(S)):
  3.         if S[i:j] contain T:
  4.             记录i,j
  5.             break
  • 接下来的问题是，伪代码中的 contain 怎么实现？ 双指针——滑动窗口 - 图4contain 操作的， 因此，
  • 双指针——滑动窗口 - 图5移动的过程中， 我们应该迭代的判断 双指针——滑动窗口 - 图6是否包含所有元素。 即双指针——滑动窗口 - 图7每移动一次， 都有可能改变了 覆盖状态 。那么， 什么时候状态会改变呢？ 什么时候状态满足了覆盖呢？
  • 题目中等价条件是包含 T 的一个全排列， 全排列有什么性质？元素个数和种类一致， 所以我们把 T 的全排列抽象出一个· target结构， 这个结构记录 T 中的排列特征， 即元素种类和对应的元素个数。显然， target 使用映射类型合适。
  • 相似的， 我们增加一个·有效窗口 window 记录满足双指针——滑动窗口 - 图8的元素， 因为这些元素才可能改变覆盖状态。
  • 综上

双指针——滑动窗口 - 图9

  1. target = {T元素种类: 元素个数}
  2. for i in range(0, len(S)):
  3.     for j in range(1, len(S)):
  4.        if S[j] in T:
  5.         window[S[j]]++        # 改变window
  6.         if window == target:  # S_ij 出现了全排列
  7.             # 记录长度
  8.             # 记录起始点
  9.             break
  • 现在又出现一个问题， 迭代过程中， 只对双指针——滑动窗口 - 图10所指的字符进行处理， 双指针——滑动窗口 - 图11所指向的字符并未处理。最小字串覆盖两端必然都是 T 中字符，所以要剔除左边不需要的字符， 即剔除多余字符 ```python target = {T元素种类: 元素个数}

for j in range(0, len(S)): if S[j] in T: window[S[j]]++ # 改变window if window == target: # S_ij 出现了全排列

  1.         # 记录长度
  2.         # 记录起始点
  4.  # S_ij是包含已经满足条件， 但是有多余字符
  5.  while window == target:
  6.         # 剔除多余字符
  7.         i++ # 在这更新i, 外层循环就不要了， 
  8.         # 必要时更新window
  9.         if S[i] in T:
  10.             window[S[i]]--
  2. - 在比较 `window = target` 需要耗费很多时间， 因此使用 `flag` 来判断两个数组接近程度。再做一些细节修改， 就得到滑动窗口算法了。
  3. <a name="3FD67"></a>
  4. # 滑动窗口
  6. - ![](https://cdn.nlark.com/yuque/__latex/a1df091f40684800d6a37b4343ec8ecb.svg#card=math&code=%5Bleft%2C%20right%29%2C%20%5C%20%E4%B8%BA%E4%B8%80%E4%B8%AA%E7%AA%97%E5%8F%A3%EF%BC%8C%20%E6%98%BE%E7%84%B6right-left%E4%B8%BA%E7%AA%97%E5%8F%A3%E9%95%BF%E5%BA%A6%20%20&height=24&width=386), 初始![](https://cdn.nlark.com/yuque/__latex/be234e9f0a17b2b5184bbf20de0cc288.svg#card=math&code=left%3Dright%3D0&height=18&width=119), 即长度为0
  7. - ![](https://cdn.nlark.com/yuque/__latex/a6c19c48d7831cd73fdb3c38cfb412bd.svg#card=math&code=left%E7%BC%A9%E5%B0%8F%E7%AA%97%E5%8F%A3%2C%20right%E6%89%A9%E5%A4%A7%E7%AA%97%E5%8F%A3%20&height=24&width=198)
  8. ```python
  9. """
  10. 给定字符串S, 目标字符串T，
  11. """
  14. def min_substring(S: str, T: str) -> str:
  17.     # 记录当前有效字符， 暂时称为有效窗口
  18.     window = {}
  20.     # 目标字符
  21.     target = {}
  22.     for c in T:
  23.         temp = target.get(c, 0)
  24.         target[c] = temp + 1
  26.     # 窗口初始， [left, right）
  27.     left:int = 0
  28.     right:int = 0
  30.     # 最小，全局最小
  31.     min_start:int = 0
  32.     min_length = len(S) + 1
  34.     # 极小,局部最小
  35.     local_start:int = 0
  36.     local_length:int = min_length
  38.     # flag, 记录匹配了几个字符。 left, right) 是一个覆盖窗口当且仅当windows = target， 即【left, right）覆盖 T
  39.     flag = 0
  41.     while right < len(S):
  42.         c = S[right]
  43.         # 窗口右边扩大
  44.         right += 1
  46.         if c in target.keys(): # 当前字符时候是有效字符， 有效字符需要更新有效窗口
  47.             temp = window.get(c, 0)
  48.             window[c] = temp + 1
  50.             # 前面更新了window有效窗口， 这时，需要判断是否为覆盖窗口
  51.             if window[c] == target[c]: # 这个字符已经完成匹配， 包括个数
  52.                flag += 1
  54.         # 窗口扩大，是否是覆盖窗口，如果是覆盖窗口则进行收缩。 由覆盖 -> 极小覆盖
  56.         while flag == len(target): # 已经覆盖， 现在求一个极小覆盖
  57.             # 初始极小覆盖长度， 起点
  58.             local_start = left
  59.             local_length = right - left
  60.             c = S[left]
  61.             # 窗口左边缩小
  62.             left += 1
  64.             if c in target.keys():# 当前字符是有效字符， 需要更新有效窗口和flag
  65.                 if window[c] == target[c]: # 如果当前c刚好匹配， window变化将改变其flag，
  66.                     flag -= 1
  68.                 window[c] -= 1
  70.         # 更新最小覆盖
  71.         if local_length < min_length:
  72.             min_start = local_start
  73.             min_length = local_length
  76.     if min_length == len(S) + 1:
  77.         return ''
  78.     return min_start, min_length
  81. if __name__ == '__main__':
  82.     print(min_substring('ccadddd', 'cca'))

总结

  • 对于双重循环, 可以考虑双指针
  • flag 更新规则， flag 反映的时双指针——滑动窗口 - 图12和 T 接近程度
  • 滑动窗口常用来解决字串问题