滑动窗口算法

尺寸法

在区间操作时，用两个指针同时遍历区间，从而实现高效操作。 限制：i < j, 一般用于区间操作

可以把需要两重遍历的操作 转变为一重循环操作 模板

for(let i = 0, j = n-1; i < j; i++,j--) {
  // 遍历操作
}

while实现模板

let s = 'xxx'
let n = s.length
let i = 0, j=n-1
while(i<j) {
  // do something
  i++,j-- // 移动指针
}

判断是否回文字符串

# 判断是否回文字符串

def isHuiwen(s:str):
  n = len(s)
  i = 0
  j = n-1
  while i <j:
    if(s[i] != s[j]):
      print(f"N")
      break
    i += 1
    j -= 1

  print(f"Y")

反向扫描

同向扫描

滑动窗口算法

维护一个窗口大小，左边向右滑，缩小窗口，右边向优化，增大窗口，滑来滑去，找到最佳答案

滑动窗口算法逻辑如下

int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

算法框架

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

LeetCode 76.查找最小覆盖子串 刷题

class Solution:
    def minWindow(self, s: str, t: str) -> str:
      '''
      暴力破解，穷举法
      '''
      # 当前滑动窗口中需要的各元素的数量
      need=collections.defaultdict(int)
      for c in t:
          need[c]+=1
      needCnt=len(t) # 所需元素的总数量
      left=0 # 窗口左边界
      res=(0,float('inf'))
      for right,c in enumerate(s):
          # right 窗口有边界
          # 包含待查找的子串，窗口左边缩小
          if need[c]>0:
              needCnt-=1

          # need中所有元素的数量都小于等于0时，表示当前滑动窗口不再需要任何元素。
          need[c]-=1 #遍历，need[c]==0时表示，刚好包含其中一个对应的元素，
          if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
              while True:      #步骤二：左边窗口缩小，排除多余元素
                  c=s[left]
                  if need[c]==0: # 元素个数刚好满足
                      break
                  need[c]+=1 # 对应的子串字符数减少
                  left+=1 # 窗口左边缩小
              if right-left<res[1]-res[0]:   #记录结果
                  res=(left,right)
              need[s[left]]+=1  #步骤三：left增加一个位置，窗口右边放大，寻找新的满足条件滑动窗口
              left+=1 # 窗口缩小右移
              needCnt+=1 # 需要元素个数+1
      return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果