滑动窗口

双指针中实现滑动窗口：核心就是右指针动时左指针不动，左指针动时，右指针不动。
举个例子，左右指针初始时都在起点，先让右指针动，此时左指针在初始位置不动，当满足搜索条件时，右指针不动，此时左右指针形成一个搜索区，而且搜索区中是符合搜索条件的，在让左指针向右移动，逐步减少搜索范围，当左指针移动到下一位置时，搜索区域就不符合搜索条件，那吗在让右指针向右移动，移动到符合搜索条件的位置，以此循环
视频：https://www.aliyundrive.com/s/yrivtJMo3on

题目

image.png

解题

可以查看上面的视频。 这道题要让我们在字符串中找到涵盖字符串t中的最小子串，而且字符串t是会有重复字符的，那就得对字符串t统计字符出现的次数，以及所需要的匹配字符串的个数。而这个最小子串那不就是说明字符串t中的字符都要出现，那就统计字符出现的次数，开始要t中的字符的出现的次数都为初始值1，当里面有重复值让其出现的次数+1，然后使用右指针去寻找符合规则的字符区域，每找到一个符合规则的字符，让其它所对应的出现的次数-1，同时让其所需要匹配的字符串个数-1,但是有可能会出现区域中出现重复字符，导致其出现次数为负值，此时就不能让其匹配的字符串个数-1。当其匹配字符串的个数为0时说明字符串t中的字符全找到啦，那就要停止右指针，让其左指针减少范围，让左指针向右移动，同时匹配左指针所指的字符是否符合字符串t中的字符，当其符合就将符合区域截取下来，保存左指针到右指针的距离。同时让其字符出现的次数+1，但是次数大于0才能让右指针动，因为可能区域内有的字符出现的次数为负值，而且要求最小子串，所以继续让左指针向右走，当左指针移动到下一位置，搜搜区域并没有t字符串中的所有字符时，让其右指针再次往右移动，再次寻找适合的搜索的的区域。而最后找到的肯定符合字符串t的最小子串

  1. /**
  2.  * @param {string} s
  3.  * @param {string} t
  4.  * @return {string}
  5.  */
  6. var minWindow = function(s, t) {
  7.     let str ='';
  8.     // 左指针
  9.     let l = 0;
  10.     // 字典 存放字符出现的次数 t中可能出现重复字符
  11.     const map = new Map()
  12.     for(let i = 0; i < t.length; i++){
  13.         const curValue = t[i];
  14.         map.set(curValue, map.get(curValue) ? map.get(curValue) + 1 : 1 )
  15.     }
  16.     //需要集齐的字符数量 
  17.     let count = t.length;
  18.     // 符合规则字符串的长度
  19.     let minLen = s.length;
  20.     //  当map中有当前字符，就将当前字符的出现次数减一，当 <= 0说明该字符已找到
  21.     //  count-- 当count === 0 说明全部找齐，更新minlen的长度 
  22.     // 判断左指针的位置向右移动后，是否还符合条件， 符合条件左指针继续移动
  23.     // r 为右指针
  24.     for(let r = 0; r < s.length; r++) {
  25.         const curValue = s[r];
  26.         if(map.has(curValue)) {
  27.             // 判断出现次数减减后是否大于0 小于零说明该字符多次出现
  28.             map.set(curValue, map.get(curValue) - 1);
  29.             if(map.get(curValue) >= 0){
  30.                 count--;
  31.             }
  32.         }
  33.         // count 等于零时说明已经找齐所有字符
  34.         while(count === 0) {
  35.             // 是否小与最小字符串长度，
  36.             if(r - l < minLen) {
  37.                 minLen = r - l ;
  38.                 str = s.slice(l, r + 1)
  39.             }
  40.             // 判断左指针当前指定的值是否为寻找的字符
  41.             const lCurVal = s[l];
  42.             if(map.has(lCurVal)) {
  43.                 map.set(lCurVal, map.get(lCurVal) + 1);
  44.                 if(map.get(lCurVal) > 0) count++
  45.             }
  46.             ++l;
  48.         }
  49.     }
  50.     return str
  51. };

牺牲有点空间，提高一点时间

  1. /**
  2.  * @param {string} s
  3.  * @param {string} t
  4.  * @return {string}
  5.  */
  6. var minWindow = function (s, t) {
  7.   let l = 0;
  8.   let r = 0;
  9.   let res = '';
  10.   const m = new Map();
  11.   for (let i = 0; i < t.length; i++) {
  12.     const c = t[i];
  13.     m.set(c, m.has(c) ? m.get(c) + 1 : 1);
  14.   }
  16.   let needType = m.size;
  17.   while (r < s.length) {
  18.     const c = s[r];
  19.     if (m.has(c)) {
  20.       m.set(c, m.get(c) - 1);
  21.       if (m.get(c) === 0) {
  22.         needType -= 1;
  23.       }
  24.     }
  25.     while (needType === 0) {
  26.       const c2 = s[l];
  27.       let newRes = s.slice(l, r + 1);
  28.       if (!res || newRes.length < res.length) res = newRes;
  29.       if (m.has(c2)) {
  30.         // 更新表中需要出现的次数
  31.         m.set(c2, m.get(c2) + 1);
  32.         if (m.get(c2) === 1) needType += 1;
  33.       }
  34.       // 移动左指针
  35.       l++;
  36.     }
  37.     // 移动右指针
  38.     r++;
  39.   }
  40.   // 返回结果值
  41.   return res;
  42. };