当前位置：首页 > article >正文

滑动窗口算法第一弹（长度最小的子数组，无重复字符的最长子串最大连续1的个数III）

article 2024/11/16 1:45:09

前言

1. 长度最小的子数组

（1）题目及示例

（2）暴力解法

（3）优化

2. 无重复字符的最长子串

（1）题目及示例

（2）暴力解法

（3）优化

3. 最大连续1的个数III

（1）题目及示例

（2）思路分析

（3）代码

前言

本文将深入剖析三道LeetCode题目，从基础的暴力解法出发，逐步阐述如何通过逻辑推理和算法优化，过渡到高效的滑动窗口算法。文章将配备图文并茂的解析，助您深入理解每一步的优化过程。

1. 长度最小的子数组

（1）题目及示例

题目：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

链接：. - 力扣（LeetCode）

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3]是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]

输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]

输出：0

（2）暴力解法

题目要求找出长度最短且相加大于等于target的子数组。暴力解法就是找出所有符合题目要求的子树，并比较其中哪个长度最短。具体解法如下：

暴力解法是固定第一个元素，加上后面的元素，直到加上后面某个元素之和大于等于target，记录下此时子数组的长度大小。
之后，再固定第二个元素，往后加上元素求和，直到符合题目要求，计算出子数组的长度大小，与之前子数组的长度进行比较，记录下较小的长度。
当固定到最后一个元素时，就已经找完了该数组内所有的子数组组合。返回记录长度的整型变量，便是最短子数组的长度。

下图是示例一中的数组，从第一个位置开始往后找符合题目要求的数组。假如最坏的情况下，每次都要找到最后一个元素，那么查找次数就是 $\frac{n\left ( n-1 \right )}{2}$ 次，只需要取最高级别，那么时间复杂度是 $O\left ( n^{2} \right )$ 。

代码如下：

    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int length = INT_MAX;
        for(int i = 0; i < nums.size(); i++)
        {
            int sum = 0;
            for(int left = i, right = i; right < nums.size(); right++)
            {
                if (sum < target)
                    sum += nums[right];
                else
                    length = fmin(length, right - left + 1)
            }
        }
        
        if (length == INT_MAX)
            return 0;
        else
            return length;
    }

（3）优化

如下图，假设蓝线表示一个抽象数组，抽象数组具有一般性，后面的题目都会从不失一般性的情况下分析。

left和right整型变量记录数组下标，表示指向数组中的某个元素。sum变量定义为从left指向的元素一直加到right指向的元素。
因为这些变量具有指向性，属于是双指针算法。后面我会以指针来称呼这些变量，且提到某变量指针前移或者后移，指向前面的元素或者后面的元素，本质是该变量的值加一或减一。

因为数组中的元素是正整数，如果right指针往后移动，那么sum2>sum1，具有递增的趋势，反之则有递减的趋势。如果left指针移动往后移动，sum值会减小，反之就会增加。这些特性很重要！

left指针固定，right指针向后移动，sum不断增加，直到sum大于等于target。此时，按照暴力解法left往后移动一个位置，right指针从left指针位置开始，sum值不断加上right指针指向的值。

当right指针重新回到之前的位置时，根据我们上面分析得出的特性，此时sum一定是小于target，所以不需要把right指针再次往后移动，只需要把left指针往后移动，就可以减少遍历次数，然后right指针再重复之前的操作，向后移动。

因此，你会发现left指针和right指针只需要往后移动，像这种双指针只朝着一个方向移动的算法，通常叫做滑动窗口。

滑动窗口解决问题的模版是：初始化变量、进窗口、出窗口、判断条件和更新结果。窗口就是双指针之间维护的元素，窗口的左边界是left指针，窗口的右边界是right指针。

进窗口是双指针之间增加一个元素，一般是right指针往后移动。出窗口是双指针之间除去一个元素，一般是left指针往后移动模版是死的，题目是活的，具体问题需要具体分析。

首先定义left、right、sum和length整型变量。left和right初始化为0，sum初始化为第一个元素，length初始化为INT_MAX，INT_MAX整型的最大值，length表示子数组的长度。
使用while循环，条件是right指针不超出数组的范围。
如果sum小于target，就要进窗口，即right指针后移，sum更新。不过需要判断right指针是否在数组的范围内。
如果sum大于等于target，先要更新length变量，使用fmin函数，比较闯入的两个参数返回更小的参数。再出窗口，即sum减去left指向的元素，left指针后移。
最后，如果length等于INT_MAX，说明结果没有更新过，没有符合要求的子数组，返回0。剩下的情况，返回length。

    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int left = 0, right = 0, n = nums.size();
        int sum = nums[0], length = INT_MAX;                                                                                                                                                                                                                                                                                                  

        //利用滑动窗口
        while(right < n)
        {   
            //进窗口
            //sum小于target，right++，sum更新
            if (sum < target)
            {
                if (++right == n)
                    break;
                    
                sum += nums[right];
            }
            else//出窗口
            {
                //sum大于或等于，length等于区间长度，并且left++，sum更新
                //right-left+1就是指针之间元素的个数
                length = fmin(length, right - left + 1);
                sum -= nums[left++];
            }
        }
        if(length == INT_MAX)
            return 0;

        return length;
    }

滑动窗口解法中，两个指针只会朝着一个方向移动。考虑最坏情况，就是两个指针都遍历整个数组，如果数组个数为n，那么就是遍历了2n次，那么时间复杂度是O(n)。

2. 无重复字符的最长子串

（1）题目及示例

题目：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

链接：. - 力扣（LeetCode）

示例 1:

输入：s = "abcabcbb" 输出：3

解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入：s = "bbbbb"

输出：1

解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 2:

输入：s = "pwwkew"

输出：3

解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

（2）暴力解法

这道题的暴力解法和上道题类似。固定所有字符字符，找出所有符合要求的子字符串，然后再比较字符串长度大小，记录下最长子字符串的长度。

至于怎么判断有无重复字符，可以使用哈希表，或者使用可以创建128位元素的数组，128位可以涵盖一般字符的ASCII码值，那么元素值就代表对应字符出现的次数。

假设字符串s = "dabcbcf"，按照暴力解法，需要固定七次，再寻找符合要求的子字符串。最坏的情况就是字符串中没有重复的字符，每次都要走到最后一个字符，假设字符串长度为n，查找次数等于n-1+n-2+……+2+1，相当于 $\frac{n\left ( n-1 \right )}{2}$ 次，那么时间复杂度是 $O\left ( n^{2} \right )$ 。

（3）优化

在暴力解法中，使用left和right整型变量表示字符串中字符的下标，因为变量具有指向性，我会称之为指针。我们固定left指针位置，right指针往后移动加入不重复的字符。

如下图，你会发现在有重复'b'字符的区域中，当right指针指向第二个‘b’字符时，left指针会指向‘a’字符，然后right指针从‘a’出发，还是会停在第二个‘b’字符中，直到left指针指向重复字符后的字符时，才会跳出这个区域。而在其中寻找的子字符串长度都比一开始的要小。

因此，我们可以从这点进行优化。当出现重复字符时，不用循规蹈矩，将right指针移动到left指针后的字符，继续寻找字符。我们仅需要将left指针往后移动寻找重复的字符，找到重复字符后，如果使用数组模拟哈希表，对应字符的元素值减一，left指针再移动到后一个字符。

此时，left指针需要固定，right指针需要向后移动，直到碰到重复的字符串，该字符串的长度跟原先记录长度值比较大小，更新结果。

代码如下：

    int lengthOfLongestSubstring(string s) 
    {
        int n = s.size();
        int left = 0;   //窗口左边界
        int right = 0;  //窗口右边界
        int len = 0; //记录字符串长度
        int hash[128] = { 0 }; //使用数组模拟哈希表

        while(right < n)
        {
            hash[s[right]]++;  //进窗口
            while(hash[s[right]] > 1)//判断
            {
                hash[s[left]]--;//出窗口，直到找到重复字符
                left++;
            }
            len = max(len, right - left + 1);//更新结果
            right++;  //让下一个元素进入窗口
        }
        
        return len;
    }

3. 最大连续1的个数III

（1）题目及示例

题目：给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

链接：. - 力扣（LeetCode）

示例 1:

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2

输出：6

解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2:

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3

输出：10

解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1
0 <= k <= nums.length

（2）思路分析

我们创建两个整型变量left和right，代表数组下标进行遍历操作。一般是left指向第一个元素，并固定left指针。right指针向后移动，如果遇到1就继续；如果遇到0，要看双指针区间内0的个数是否小于整数K，小于就继续后移，不小于就停止。

跟之前两道题目类似，暴力解法就是按照上面的方法固定每个元素，找出所有符合要求的序列，比较所有序列个数的大小。但是这个方法查找效率较低，如果该序列没有0，那就要查找 $n^{2}$ 级别次数，时间复杂度是 $O\left ( n^{2} \right )$ 。

但是我们可以转换一下这个问题，找出不超过K个0的序列，再从满足该要求的序列中找出元素个数最大的序列。再遇到上面的情况时，我们会发现固定left指针后一个元素，right指针从left指针开始向后移动，还是会在停在之前的位置。

不仅是后面的元素，前四个元素中，right都会停在之前的位置，因为双指针中0的个数超过K个。并且连续1的个数不会大于该区间内第一个元素开始的序列。

因此，遇到双指针内0的个数超过K时，先移动left指针。我们再定义一个变量zero，来记录双指针间0出现的个数。left指针向后移动的过程中，如果遇到1，直接跳过；如果遇到0，zero变量减1。当zero<=K时，此时双指针间的序列符合题目要求，移动right指针，重复上面的过程。

每次找到符合要求的序列，如果是第一次，用len变量记录其个数。如果不是第一次，len变量要跟新符合要求的序列个数进行比较，如果len大，就不用更行len变量，反之就要更新。

（3）代码

此题目还是使用滑动窗口解决问题。下面是解释代码的步骤：

一开始初始化left，right，zero和len变量都为0。
使用while循环，循环条件是right变量小于原数组的个数，即right指针指向的元素不要超出数组的范围。
当right指针遇到0，就要进窗口，即zero就加一。当zero>K时，移动left指针，遇到0时，就要出窗口，即zero减一，直到zero小于等于K。做完这些操作，更新一下len。right指针加加。

    int longestOnes(vector<int>& nums, int k) 
    {
        int left = 0, right = 0; //左窗口和右窗口
        int zero = 0, len = 0;   //记录0出现个数和窗口元素个数

        while(right < nums.size())
        {
            if (nums[right] == 0)//进窗口
                zero++;

            while(zero > k)//判断
            {   
                if (nums[left++] == 0)//出窗口    
                    zero--;
            }
    
            len = max(len, right - left + 1);//更新结果
            right++;
        }

        return len;
    }

创作不易，希望这篇文章能给你带来启发和帮助，如果喜欢这篇文章，请留下你的三连，你的支持的我最大的动力！！！