滑动窗口（一）

一.滑动窗口的介绍

滑动窗口算法是一种优化的线性时间复杂度算法。

从概念上讲，它就像是在数据序列（如数组或字符串）上有一个可以“滑动”的窗口。这个窗口大小可以固定，也可以根据条件动态变化。

主要用于解决一些连续区间相关的问题，比如在一个很长的数组中寻找满足某种条件的子数组，像子数组的和大于某个值、子数组内元素的乘积小于给定值等。或者在字符串中，找最长无重复字符的子串之类的问题。

其优势在于能够减少不必要的计算。以在数组中求固定长度滑动窗口内元素和为例，普通方法可能会对每个窗口都重新计算元素和，但滑动窗口算法只需在前一个窗口的和基础上，减去滑出窗口的元素，加上滑入窗口的元素，就可以快速得到新窗口的和，从而高效地利用了之前的计算结果。

二.经典题目讲解

1.长度最长的子数组

题目链接

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
            int left = 0;
            int right = 0;
            int sum = 0;
            int len=10000;
            while(right<nums.length){
                sum +=nums[right];
                while(sum>=target){
                 len = Math.min(len,right-left+1);
                  sum -=nums[left++];
                }
                right++;
            }
           return len == 10000? 0 : len;
    }
}

本题我们先思考为什么要用滑动窗口，以及滑动窗口是一个什么样的思想？

以数组【2,3，1,2，4,3】 target=7来举例:
先定义一个left指针，接着定义一个right指针

根据双指针思想，使right指针逐步后移。定义sum变量，将right指针所对应下标的值依次累加到sum中。若sum的值大于target，则停止累加；若sum的值小于等于target，则继续累加。

按照双指针的思路，让right指针逐步向后移动。定义一个sum变量，不断把right指针所对应下标的元素累加到sum里。当sum大于target时，就停止累加操作；若sum小于等于target，就持续累加。

例如，当right停在索引为2的元素位置时，sum = 8大于7（假设7为target值），此时从left到right的元素之和满足要求（大于target），元素个数为right - left + 1等于4。我们可将从left到right的元素视为一个窗口，其大小为right - left + 1。定义变量len来保存这个窗口的大小。

接着让left往后移动一个元素

此时，right没有必要回退到left元素处。依据单调性，由于前面计算得到2 + 3+ 1 + 2 = 8 > 7，当left移动到3的位置时，此时sum的值为3 + 1+ 2，必然小于7。这是因为left从第一个2的位置移动到3的位置，所以sum需要减去原来left位置的值，即sum = 8 - 2 = 6，又因为6 < target，所以让right继续保持在原来的位置，然后往后继续移动。

当right移动到4这个位置时，由于3 + 1 + 2+ 4大于target（也可表示为sum + 4），这就又满足了条件。此时便出现了一个新的满足条件的窗口，其大小为right - left + 1。我们需要比较上一次的窗口和这一次窗口的大小，然后保留较小的那个窗口。从直观上看，这个窗口就像是在平移一样，所以被称为滑动窗口。

在这个时候，窗口的大小仍然是4，因为sum大于target，所以left指针向前移动一位（left++），然后重复这样的操作。

1. 关于为什么使用滑动窗口

• 题目要求找到和大于等于target的最小子数组长度。滑动窗口这种算法技巧非常适合解决这类连续子数组相关的问题。
  • 滑动窗口的基本思想是通过双指针（在这个代码中是left和right）维护一个“窗口”，这个窗口内的元素之和是我们关注的量。通过不断调整窗口的左右边界，可以高效地遍历数组的所有子数组（以一种有序的、不重复的方式），从而找到满足条件的最小子数组长度。
  • 相比于暴力解法（枚举所有可能的子数组并计算其和），滑动窗口算法大大减少了计算量，因为它避免了对已经计算过的子数组部分的重复计算。
  2. 代码解释
  • 初始化部分
  • int left = 0;和int right = 0;：这是定义滑动窗口的左右边界指针，初始时都指向数组的第一个元素。
  • int sum = 0;：用于记录当前滑动窗口内元素的和。
  • • int len = 10000;：这是一个初始的较大值，用于记录满足条件的最小子数组长度。
      外层while循环
      - while(right < nums.length)：这个循环的目的是不断扩大滑动窗口的右边界，直到右边界到达数组的末尾。
      - - - 在循环内部，首先执行len = Math.min(len, right - left+1);，这是计算当前窗口的长度（right - left + 1）并与之前记录的最小长度len比较，如果当前长度更小，则更新len。
      - - 然后执行sum -= nums[left++];，这是将左边界向右移动一位，同时从sum中减去移出窗口的元素的值。

假设我们有target = 7，数组nums = [2,3,1,2,4,3]。

1. 初始化：
   • left = 0，right = 0，sum = 0，len = 10000。
2. 第一次外层while循环：
   • 当right = 0时，sum = nums[0]=2。此时sum < target，right向右移动。
3. 当right = 1时：
   • sum = nums[0]+nums[1]=2 + 3=5。sum < target，right继续向右移动。
4. 当right = 2时：
   • sum = nums[0]+nums[1]+nums[2]=2 + 3+1 = 6。sum < target，right继续向右移动。
5. 当right = 3时：
   • sum = nums[0]+nums[1]+nums[2]+nums[3]=2+3 + 1+2 = 8。此时sum>=target，进入内层while循环。
   • 计算当前窗口长度为right - left+1 = 3 - 0+1 = 4，更新len = Math.min(len,4)，此时len = 4。
   • 然后sum -= nums[left++]，即sum = sum - nums[0]=8 - 2 = 6，left = 1。
   • 此时sum < target，跳出内层while循环，right继续向右移动。
6. 当right = 4时：
   • sum = nums[1]+nums[2]+nums[3]+nums[4]=3+1+2 + 4 = 10。sum>=target，进入内层while循环。
   • 计算当前窗口长度为right - left+1 = 4 - 1+1 = 4，len保持为4（因为Math.min(len,4)，len已经是4了）。
   • 然后sum -= nums[left++]，即sum = sum - nums[1]=10 - 3 = 7，left = 2。
   • 此时sum>=target，再次进入内层while循环。
   • 计算当前窗口长度为right - left+1 = 4 - 2+1 = 3，更新len = Math.min(len,3)，此时len = 3。
   • 然后sum -= nums[left++]，即sum = sum - nums[2]=7 - 1 = 6，left = 3。
   • 此时sum < target，跳出内层while循环，right继续向右移动。
7. 当right = 5时：
   • sum = nums[3]+nums[4]+nums[5]=2+4+3 = 9。sum>=target，进入内层while循环。
   • 计算当前窗口长度为right - left+1 = 5 - 3+1 = 3，len保持为3。
   • 然后sum -= nums[left++]，即sum = sum - nums[3]=9 - 2 = 7，left = 4。
   • 此时sum>=target，进入内层while循环。
   • 计算当前窗口长度为right - left+1 = 5 - 4+1 = 2，更新len = Math.min(len,2)，此时len = 2。
   • 然后sum -= nums[left++]，即sum = sum - nums[4]=7 - 4 = 3，left = 5。
   • 此时sum < target，跳出内层while循环。
8. 外层while循环结束后：
   • 由于len不等于10000，所以返回len = 2，即满足和大于等于7的最小子数组长度为2。

2.无重复字符串

无重复字符串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] ss = s.toCharArray();
        int left = 0;
        int right = 0;
        int v = 0;
        int[] hashmap = new int[128];
        while (right < ss.length) {
            hashmap[ss[right]]++;
            while (hashmap[ss[right]] > 1) {
                hashmap[ss[left++]]--;
            }
            v = Math.max(v, right - left+1);
            right++;
        }
        return v;
    }
}

以abcab举例，定义一个Left和right指针

创建一个数组用来记录每个字符在当前窗口内出现的次数，数组的下标对应字符的ASCII码值，数组的值表示该字符出现的次数。

right一直加加直到遇到重复字符为止。

当right的下标为3时，恰好遇到了重复字符‘a’，此时right - left + 1所表示的就是当前无重复字符串的个数。不过，我们还不能确定这个无重复字符串就是最长的子串，还需要继续进行比较。

一旦遇到不符合题意的情况，就需要更新窗口的大小，让left的值加1。例如，此时我们要判断从left为1开始之后的无重复子串的大小，很明显，要让下标为0的元素从窗口中移除出去。

1. 整体思路

• 这道题是要找出给定字符串中最长的无重复字符的子串长度。这里使用了滑动窗口的思想，通过双指针left和right来维护一个窗口，并且使用一个大小为128的数组hashmap（因为ASCII字符集最多有128个字符）来记录每个字符在当前窗口内出现的次数。

2. 代码解释

• 初始化部分
  • char[] ss = s.toCharArray();：将输入的字符串s转换为字符数组，这样方便后续对每个字符进行操作。
  • int left = 0;和int right = 0;：这是滑动窗口的左右边界指针，初始时都指向字符串的开头。
  • int v = 0;：用于记录到目前为止找到的最长无重复字符子串的长度。
• int[] hashmap = new int[128];：创建一个数组用来记录每个字符在当前窗口内出现的次数，数组的下标对应字符的ASCII码值，数组的值表示该字符出现的次数。
  • 外层while循环
  • while (right < ss.length)：这个循环的目的是不断扩大滑动窗口的右边界，直到右边界到达字符串的末尾。
    • 在每次循环中，首先执行hashmap[ss[right]]++;，这是将新进入滑动窗口（右边界向右移动一位）的字符的计数加1，表示该字符在窗口内出现的次数增加了。
      内层while循环
    • while (hashmap[ss[right]]>1)：这个循环的目的是当窗口内出现重复字符（即某个字符的计数大于1）时，通过移动左边界来调整窗口，直到窗口内不再有重复字符。
      • 在循环内部，执行hashmap[ss[left++]]--;，这是将左边界向右移动一位，同时将移出窗口的字符的计数减1，表示该字符在窗口内出现的次数减少了。
        计算最长子串长度部分
• 在每次外层while循环中（无论是内层while循环调整窗口后还是不需要调整窗口时），都会执行v = Math.max(v, right - left + 1);，这是计算当前窗口的长度（right - left+1）并与之前记录的最长长度v比较，如果当前长度更大，则更新v。

1. 假设输入字符串s = "abcabcbb"。

   • 初始化：
     • 转换为字符数组后ss = ['a','b','c','a','b','c','b','b']。
     • left = 0，right = 0，v = 0，hashmap数组初始值全为0。
   • 第一次外层while循环（right = 0）：
     • hashmap[ss[right]]++;，此时hashmap['a'] = 1。
     • 因为hashmap[ss[right]] = 1（不大于1），所以直接执行v = Math.max(v, right - left+1)，此时v = Math.max(0,0 - 0+1)=1。然后right++，right变为1。
   • 第二次外层while循环（right = 1）：
     • hashmap[ss[right]]++;，此时hashmap['b'] = 1。
     • 因为hashmap[ss[right]] = 1（不大于1），所以执行v = Math.max(v, right - left+1)，此时v = Math.max(1,1 - 0+1)=2。然后right++，right变为2。
   • 第三次外层while循环（right = 2）：
     • hashmap[ss[right]]++;，此时hashmap['c'] = 1。
     • 因为hashmap[ss[right]] = 1（不大于1），所以执行v = Math.max(v, right - left+1)，此时v = Math.max(2,2 - 0+1)=3。然后right++，right变为3。
   • 第四次外层while循环（right = 3）：
     • hashmap[ss[right]]++;，此时hashmap['a'] = 2。
     • 因为hashmap[ss[right]]>1，进入内层while循环。
       • 执行hashmap[ss[left++]]--;，此时left从0变为1，hashmap['a']变为1。
     • 执行v = Math.max(v, right - left+1)，此时v = Math.max(3,3 - 1+1)=3。然后right++，right变为4。
   • 第五次外层while循环（right = 4）：
     • hashmap[ss[right]]++;，此时hashmap['b'] = 2。
     • 因为hashmap[ss[right]]>1，进入内层while循环。
       • 执行hashmap[ss[left++]]--;，此时left从1变为2，hashmap['b']变为1。
     • 执行v = Math.max(v, right - left+1)，此时v = Math.max(3,4 - 2+1)=3。然后right++，right变为5。
   • 第六次外层while循环（right = 5）：
     • hashmap[ss[right]]++;，此时hashmap['c'] = 2。
     • 因为hashmap[ss[right]]>1，进入内层while循环。
       • 执行hashmap[ss[left++]]--;，此时left从2变为3，hashmap['c']变为1。
     • 执行v = Math.max(v, right - left+1)，此时v = Math.max(3,5 - 3+1)=3。然后right++，right变为6。
   • 第七次外层while循环（right = 6）：
     • hashmap[ss[right]]++;，此时hashmap['b'] = 2。
     • 因为hashmap[ss[right]]>1，进入内层while循环。
       • 执行hashmap[ss[left++]]--;，此时left从3变为4，hashmap['b']变为1。
     • 执行v = Math.max(v, right - left+1)，此时v = Math.max(3,6 - 4+1)=3。然后right++，right变为7。
   • 第八次外层while循环（right = 7）：
     • hashmap[ss[right]]++;，此时hashmap['b'] = 2。
     • 因为hashmap[ss[right]]>1，进入内层while循环。
       • 执行hashmap[ss[left++]]--;，此时left从4变为5，hashmap['b']变为1。
     • 执行v = Math.max(v, right - left+1)，此时v = Math.max(3,7 - 5+1)=3。
   • 最后，外层while循环结束，返回v = 3，即字符串"abcabcbb"中最长无重复字符子串（如"abc"）的长度为3。

2. 再看一个例子，假设输入字符串s = "bbbbb"。

   • 初始化：
     • 转换为字符数组后ss = ['b','b','b','b','b']。
     • left = 0，right = 0，v = 0，hashmap数组初始值全为0。
   • 第一次外层while循环（right = 0）：
     • hashmap[ss[right]]++;，此时hashmap['b'] = 1。
     • 因为hashmap[ss[right]] = 1（不大于1），所以执行v = Math.max(v, right - left+1)，此时v = Math.max(0,0 - 0+1)=1。然后right++，right变为1。
   • 第二次外层while循环（right = 1）：
     • hashmap[ss[right]]++;，此时hashmap['b'] = 2。
     • 因为hashmap[ss[right]]>1，进入内层while循环。
       • 执行hashmap[ss[left++]]--;，此时left从0变为1，hashmap['b']变为1。
     • 执行v = Math.max(v, right - left+1)，此时v = Math.max(1,1 - 1+1)=1。然后right++，right变为2。
   • 以此类推，每次当right增加时，由于都是'b'字符，会进入内层while循环调整left。
   • 最后，外层while循环结束，返回v = 1，因为字符串"bbbbb"中最长无重复字符子串就是单个'b'，长度为1。