【十】【算法分析与设计】滑动窗口（1）

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的连续

子数组

[nums(l), nums(l+1), ..., nums(r-1), nums(r)] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 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

提示：

1 <= target <= 10(9)

1 <= nums.length <= 10(5)

1 <= nums[i] <= 10(5)

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

暴力枚举：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ret = INT_MAX;
        for (int start = 0; start < n; start++) {
            int sum = 0;
            for (int end = start; end < n; end++) {
                sum += nums[end];
                if (sum >= target) {
                    ret = min(ret, end - start + 1);
                    break;
                }
            }
        }
        return ret == INT_MAX ? 0 : ret;
    }
};

滑动窗口（同向指针）优化暴力枚举：

对于[left,right]区间中，如果sum>=target，此时right-left+1的长度一定是和left组合中最小的长度，left与right+1....后面的组合一定都大于target，但是长度一定比right-left+1长。所以对于left的所有组合已经全部考虑完毕。注意这里有一个隐含的信息，此时nums[left]+....+nums[right-1]<target。对于与left的所有组合都考虑完毕，sum-=nusm[left],left++。

此时left与left+1...right-1，这些数的组合一定<target。因为nums[left-1]+....+nums[right-1]<target。所以这些情况可以直接无视，当作我们已经考虑完毕。只需要再从right的位置再考虑。

如果sum<target，right++，sum+=nums[right]，直到sum>=target。以此类推

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ret = INT_MAX;
        int sum = 0;

        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                ret = min(ret, right - left + 1);
                sum -= nums[left++];
            }
        }
        return ret == INT_MAX ? 0 : ret;
    }
};

class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {

定义了一个名为 minSubArrayLen 的成员函数，它接受一个目标值 target 和一个整数数组 nums 作为参数，并返回一个整数，表示所求子数组的最短长度。

int n = nums.size();int ret = INT_MAX;int sum = 0;

获取 nums 的大小并赋值给 n，初始化 ret 为 INT_MAX 作为最短长度的最大可能值，初始化 sum 为 0 用于记录窗口内元素的总和。

for (int left = 0, right = 0; right < n; right++) { sum += nums[right];

使用双指针 left 和 right 来定义滑动窗口的边界。right 指针向右移动来扩大窗口，并将 nums[right] 加到 sum 中。

while (sum >= target) { ret = min(ret, right - left + 1); sum -= nums[left++];}

当窗口内元素总和大于等于 target 时，尝试缩小窗口来找到最短的子数组。更新 ret 为当前子数组长度和 ret 的较小值，然后将 left 指针右移并从 sum 中减去 nums[left]。

}return ret == INT_MAX ? 0 : ret;}};

最后，如果 ret 仍为 INT_MAX，表示没有找到满足条件的子数组，返回 0；否则返回 ret 作为最短子数组的长度。

时间复杂度和空间复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。尽管有一个嵌套的 while 循环，但每个元素最多被访问两次（一次由 right 指针，一次由 left 指针），所以总的时间复杂度是线性的。

空间复杂度：O(1)，算法只使用了常数级别的额外空间。

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

给定一个字符串 s ，请你找出其中不含有重复字符的最长

子串

的长度。

示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 10(4)

s 由英文字母、数字、符号和空格组成

暴力枚举：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int hash[128] = {0};
            for (int j = i; j < n; j++) {
                hash[s[j]]++;
                if (hash[s[j]] > 1)
                    break;

                ret = max(ret, j - i + 1);
            }
        }
        return ret;
    }
};

class Solution {public:int lengthOfLongestSubstring(string s) {

定义了一个名为 lengthOfLongestSubstring 的成员函数，它接受一个字符串 s 作为参数，并返回一个整数，表示无重复字符的最长子串的长度。

int ret = 0;int n = s.length();

初始化 ret 为 0 来记录最长子串的长度，获取字符串 s 的长度并赋值给 n。

for (int i = 0; i < n; i++) {

使用外层循环遍历字符串 s，i 是子串的起始位置。

int hash[128] = {0};

初始化一个哈希表 hash，用于记录子串中每个字符的出现次数。这里使用了长度为 128 的数组，是因为 ASCII 字符集共有 128 个字符。

for (int j = i; j < n; j++) { hash[s[j]]++;

使用内层循环从 i 开始遍历字符串 s，j 是子串的结束位置。每遍历一个字符，就在哈希表中对应位置的计数加一。

if (hash[s[j]] 1)break;

如果当前字符的出现次数超过了一次，说明子串中出现了重复字符，需要终止内层循环。

ret = max(ret, j - i + 1);}}

在每次内层循环中，如果没有发现重复字符，就更新 ret 的值为当前子串长度和原 ret 值的较大者。

时间复杂度和空间复杂度分析

时间复杂度：O(n^2)，其中 n 是字符串 s 的长度。因为有两层嵌套循环，每个字符都可能被检查 n 次。

空间复杂度：O(1)，尽管使用了哈希表，但其大小是固定的（128），与输入大小无关，因此空间复杂度为常数。

滑动窗口（同向双指针）优化暴力枚举：

研究[left,right]区间，如果这个区间没有重复的字符，right++，如果当right加入进来后发现有重复的字符，对于left与right+1，right+2.........这些的组合都会有重复的字符，所以我们直接跳过这些组合，对于left的所有组合都考虑完毕，left++。这里有一个隐含的信息，那就是（left还没有++时）[left,right-1]这段区间是没有重复字符的区间。（left++后）研究与left的组合情况。对于[left,right-1]这些情况一定是没有重复字符的，但是长度一定比还没有left++时的长度小，所以对于left与left+1,left+2......right-1这些数的组合可以直接跳过。直接从right的组合开始考虑。

如果[left,right]有重复字符，那么left++，直到没有重复为止。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        int n = s.length();

        int hash[128] = {0};
        int left = 0, right = 0;
        while (right < n) {
            hash[s[right]]++;
            while (hash[s[right]] > 1) {
                hash[s[left]]--;
                left++;
            }
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};

class Solution {public:int lengthOfLongestSubstring(string s) {

定义了一个名为 lengthOfLongestSubstring 的成员函数，它接受一个字符串 s 作为参数，并返回一个整数，表示无重复字符的最长子串的长度。

int ret = 0;int n = s.length();

初始化 ret 为 0 来记录最长子串的长度，获取字符串 s 的长度并赋值给 n。

int hash[128] = {0};

初始化一个哈希表 hash，用于记录子串中每个字符的出现次数。这里使用了长度为 128 的数组，是因为 ASCII 字符集共有 128 个字符。

int left = 0, right = 0;

初始化双指针 left 和 right 来定义滑动窗口的边界。这个窗口内将不会有重复的字符。

while (right < n) { hash[s[right]]++;

right 指针向右移动来扩大窗口，并将 nums[right] 对应的哈希表计数加一。

while (hash[s[right]] 1) { hash[s[left]]--; left++;}

当在哈希表中发现 nums[right] 对应的计数大于 1 时，说明窗口内出现了重复字符。此时对于left的所有组合可以理解为全部都考虑完毕。left++后，对于left与left+1....right-1这些数的组合直接跳过，如果此时还有重复的字符，表明对于此left的所有情况也全部考虑完毕。继续进行left++，直到没有重复字符为止。left 指针向右移动，并将离开窗口的字符 nums[left] 对应的哈希表计数减一。

ret = max(ret, right - left + 1);

在每次 right 指针移动之后，更新 ret 为当前窗口的大小和原 ret 值的较大者。

right++;}

right 指针继续向右移动，寻找下一个可能的最长无重复字符的子串。

时间复杂度和空间复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。尽管有一个嵌套的 while 循环，但每个字符最多被访问两次（一次由 right 指针，一次由 left 指针），所以总的时间复杂度是线性的。

空间复杂度：O(1)，尽管使用了哈希表，但其大小是固定的（128），与输入大小无关，因此空间复杂度为常数。

1004. 最大连续1的个数 III

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

示例 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 <= 10(5)

nums[i] 不是 0 就是 1

0 <= k <= nums.length

暴力枚举：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int zeroCount = 0;
        int ret = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            zeroCount=0;
            for (int j = i; j < n; j++) {
                if (nums[j] == 0)
                    zeroCount++;
                if (zeroCount > k)
                    break;
                ret = max(ret, j - i + 1);
            }
        }
        return ret;
    }
};

滑动窗口（同向双指针）优化暴力枚举：

对于与left的组合，维护一个区间[left,right)表示left与left+1，left+2......right-1这些数的组合全部考虑完毕。接着考虑与right的组合情况。如果nums[right]==0，zeroCount++。当新加入的right使得zeroCount>k，表示含有的0超过了限制，left与right的组合不符合题意，当然left与right+1.....n-1的组合也不符合题意。跳过后面的组合，对于left的所有组合情况考虑完毕。left++。(left++后)left与left+1,left+2....right-1这些数的组合符合题意，但是长度一定比还没有left++的长度小，所以对于这些组合我们也跳过。直接考虑left与right的组合。如果此时zeroCount>k,后面的组合也不用考虑，说明left的所有组合都考虑完毕了。left++，以此类推，直到zeroCount<=k。此时对于区间[left,right]已经考虑完毕，right++。

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int zeroCount = 0;
        int ret = 0;
        int n = nums.size();

        for (int left = 0, right = 0; right < n; right++) {
            if (nums[right] == 0)
                zeroCount++;
            while (zeroCount > k)
                if (nums[left++] == 0)
                    zeroCount--;
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

class Solution {public:int longestOnes(vector<int& nums, int k) {

定义了一个名为 longestOnes 的成员函数，它接受一个整数数组 nums 和一个整数 k 作为参数，并返回一个整数，表示翻转最多 k 个 0 后数组中最大连续 1 的个数。

int zeroCount = 0;int ret = 0;int n = nums.size();

初始化 zeroCount 为 0 来记录当前窗口内 0 的个数，初始化 ret 为 0 来记录最大连续 1 的个数，获取数组 nums 的长度并赋值给 n。

for (int left = 0, right = 0; right < n; right++) {if (nums[right] == 0) zeroCount++;

使用双指针 left 和 right 来定义滑动窗口的边界。right 指针向右移动来扩大窗口，并在遇到 0 时增加 zeroCount。

while (zeroCount k)if (nums[left++] == 0) zeroCount--;

当窗口内 0 的个数超过 k 时，对于left的所有组合都考虑完毕，left++，对于++后的left，如果zeroCount>k，说明对于left的所有组合也考虑完毕，left++，直到zreoCount<=k，缩小窗口直到 0 的个数不超过 k。left 指针向右移动，并在移出窗口的是 0 时减少 zeroCount。