leetcode上大概10道滑动窗口题目，难度为medium/hard

模板：

思路：

图片.png
复杂度为O(n)

模板：

  1. /* 滑动窗口算法框架 */
  2. void slidingWindow(string s, string t) {
  3.     unordered_map<char, int> need, window;
  4.     for (char c : t) need[c]++;
  6.     int left = 0, right = 0;
  7.     int valid = 0; 
  8.     while (right < s.size()) {
  9.         // c 是将移入窗口的字符
  10.         char c = s[right];
  11.         // 右移窗口
  12.         right++;
  13.         // 进行窗口内数据的一系列更新
  14.         ...
  16.         /*** debug 输出的位置 ***/
  17.         printf("window: [%d, %d)\n", left, right);
  18.         /********************/
  20.         // 判断左侧窗口是否要收缩
  21.         while (window needs shrink) {
  22.             // d 是将移出窗口的字符
  23.             char d = s[left];
  24.             // 左移窗口
  25.             left++;
  26.             // 进行窗口内数据的一系列更新
  27.             ...
  28.         }
  29.     }
  30. }

例题

经典题目问题1：最小子串

图片.png

  1. function minWindow(str,target){
  2.   let need = {},window={};
  3.   for(let t of target){
  4.       need[t] = need[t]++
  5.   }
  7.   //valid变量的设置！！！
  8.   let left = 0,right=0,valid=0;
  9.   //len长度的设置！！！
  10.   let start=0,len = Number.Max_Integer;
  11.   while(right<str.length){
  12.     let s = str[right];
  13.     right++;
  15.     if(need[s]){
  16.         window[s]++
  17.       if(window[s]===need[s]){
  18.           valid++;
  19.       }
  20.     }
  22.     while(valid===Object.keys().length){
  24.       //取start len的值,此处非常巧妙！！！！保证了最小长度
  25.       if(right-left<len){
  26.           start = left;
  27.         len = right-left;
  28.       }
  30.         const c = str[left];
  31.       left++;
  33.       if(need[c]){
  34.           if(window[c]===need[d]){
  35.             valid--;
  36.           window[c]--; 
  37.         }
  38.       }
  39.     }
  40.   }
  42.   return len==Number.Max_Integer?'':str.substring(start,len);
  43. }

问题2：字符串排列

图片.png

  1. // 判断 s 中是否存在 t 的排列
  2. bool checkInclusion(string t, string s) {
  3.     unordered_map<char, int> need, window;
  4.     for (char c : t) need[c]++;
  6.     int left = 0, right = 0;
  7.     int valid = 0;
  8.     while (right < s.size()) {
  9.         char c = s[right];
  10.         right++;
  11.         // 进行窗口内数据的一系列更新
  12.         if (need.count(c)) {
  13.             window[c]++;
  14.             if (window[c] == need[c])
  15.                 valid++;
  16.         }
  18.         // 判断左侧窗口是否要收缩
  19.         while (right - left >= t.size()) {
  20.             // 在这里判断是否找到了合法的子串
  21.             if (valid == need.size())
  22.                 return true;
  23.             char d = s[left];
  24.             left++;
  25.             // 进行窗口内数据的一系列更新
  26.             if (need.count(d)) {
  27.                 if (window[d] == need[d])
  28.                     valid--;
  29.                 window[d]--;
  30.             }
  31.         }
  32.     }
  33.     // 未找到符合条件的子串
  34.     return false;
  35. }

疑问：如果如果字母不相邻怎么办？

问题3：找所以字母异位词

图片.png

问题4：最长无重复子串

图片.png