算法-滑动窗口

1. leetcode209 长度最小的子数组

1.1 思路

首先看题干可以很明显判断出是用滑动窗口来做（要找数组中的连续子数组）。
然后是对这些事情进行判断：

• 右指针处理
• 右指针移动
• 左指针处理
• 左指针移动

显然循环中首先需要进行右指针处理，也就是把右指针的值放入窗口。
接下来要判断窗口的值总和是否大等于于target：

• 如果大于等于，进行左指针的处理和移动
• 如果小于，说明右指针可以继续移动

最终进行判断返回结果即可。

1.2 代码

var minSubArrayLen = function(target, nums) {
    let l = 0 , r = 0 , sum = 0 , cnt = Number.MAX_SAFE_INTEGER;
    while(r < nums.length) {
        sum += nums[r];
        while(sum >= target) {
            cnt = Math.min(cnt , r - l + 1);
            sum -= nums[l];
            l++;
        }
        r++;
    }
    return cnt === Number.MAX_SAFE_INTEGER ? 0 : cnt;
};

2. leetcode904 水果成篮

2.1 思路

其实和209很像，209是找滑动窗口内的值大小，这题是找滑动窗口内不同值的个数。
同样，最重要的还是要想清楚这几件事情的判断：

• 右指针处理
• 右指针移动
• 左指针处理
• 左指针移动

这题难点是左指针的移动，当然也可以一个个动来判断，不过会比较浪费时间，可以把滑动窗口内第二种数字的值记录下来，加入第三种数字时左指针直接跳到第二种数字处，那么窗口内就还是两种数字。

2.2 代码

var totalFruit = function(fruits) {
    let cnt = -1 , l = 0 , r = 0 , mark = 0;
    let arr = [fruits[0]];
    while(r < fruits.length) {
        // 对比209 这里就相当于左右指针的处理
        if(!arr.includes(fruits[r])) {
            // 一开始只有一种水果
            if(arr.length < 2) {
                arr[1] = fruits[r];
            // 已经有两种水果 来了新的 更新篮子内水果
            } else {
                // 左指针跳到新arr[0]对应的下标 比如3 3 3 1 2 右指针走到2后左指针得跳到1
                // 此时arr内容为[1 , 2]
                l = mark;
                arr[0] = arr[1];
                arr[1] = fruits[r];
            }
        }

        // 更新左指针应该跳到的下标 比如3 3 3 1 2 mark首先指向1 对应上面的代码
        if(fruits[mark] !== fruits[r]) mark = r;
        cnt = Math.max(cnt , r - l + 1);

        r++;
    }
    return cnt;
};

3. leetcode439 找到字符串中所有字母异位词

3.1 思路

预处理的步骤比如初始化，统计次数不展开分析

这题重点分析比较不同的滑动窗口思路，首先大框架是不变的，也就是上文提到的那四个步骤，这题的大致顺序和结构都和209是一样的，都是：

• 右指针处理
• 在while循环中进行左指针处理
• 在while循环中进行左指针移动
• 右指针移动

但是这题难点是怎么才能找到异位词，最直接的思路可能是维护一个和p字符串长度相等的窗口，左右指针一起每次动1位，来计算窗口中字母出现次数是否与p相同。这种做法可行，但不论是初始化还是后续代码都比较繁琐，而且时间复杂度高。

因此这题可以换个思路，也就是窗口长度不固定，当窗口长度和p相同时，说明找到了异位词。那么该怎么实现这个思路呢？还是和209类似的思路，包括很多滑动窗口用的都是这个思路：右指针犯错，左指针修复。

详细见代码：

3.2 代码

var findAnagrams = function(s, p) {
    if(s.length < p.length) return [];

    let res = [] , l = 0 , r = 0;
    let arr = new Array(26).fill(0);
    // 统计p中字符串出现次数
    for(let c of p) {
        arr[c.charCodeAt() - 'a'.charCodeAt()]++;
    }

    for(let i = 0 ; i < s.length ; i++) {
        // 减去右指针对应字母的出现次数
        let rCode = s[r].charCodeAt() - 'a'.charCodeAt();
        arr[rCode]--;
        // 如果出现<0 说明减错了 左指针来恢复
        while(arr[rCode] < 0) {
            let lCode = s[l].charCodeAt() - 'a'.charCodeAt();
            arr[lCode]++;
            l++;
        }
        // 如果窗口大小和p.length相同了都还没减错 那么说明是字母异位词
        if(r - l + 1 === p.length) res.push(l); 
        r++;
    }
    
    return res;
};

4. leetcode15 三数之和

4.1 思路

这题做过很多遍了，比较熟悉了，核心点就在于最左边的指针不动（当轮for循环内），中间指针和右指针组成滑动窗口。

要注意的点：

• 首先得给数组排序
• 注意特判，nums[i]大于0时sum肯定大于0了，直接return
• 注意去重，针对i，l，r都要去重

4.2 代码

var threeSum = function(nums) {
   let res = [];
   nums.sort((a , b) => a - b);
   
   for(let i = 0 ; i < nums.length ; i++) {
      if(nums[i] > 0) return res;
      if(i > 0 && nums[i] === nums[i - 1]) continue;
      
      let l = i + 1 , r = nums.length - 1;
      while(l < r) {
         let sum = nums[i] + nums[l] + nums[r];
         if(sum === 0) {
            res.push([nums[i] , nums[l] , nums[r]]);
            while(l < r && nums[l] === nums[l + 1]) l++;
            while(l < r && nums[r] === nums[r - 1]) r--;
            l++;
            r--;
         } else if(sum > 0) {
            r--;
         } else {
            l++;
         }
      }
   }

   return res;
};