算法实战：滑动窗口经典题深度剖析

文章标题：

算法实战：滑动窗口经典题深度剖析

文章内容：

引言

在算法的学习进程当中，滑动窗口是一种极为实用且频繁出现的解题方法。它能够高效地处理数组、字符串这类序列数据，在诸多涉及求子数组、子字符串的相关问题上表现出色。今日将为大家分享三道运用滑动窗口来解决的中等难度算法题，以及对应的代码实现和解题思路。

一、1004. 最大连续1的个数 III

题目描述

给定一个由二进制数构成的数组 nums 和一个整数 k，假定最多可以翻转 k 个 0，要求返回经过操作后数组中连续 1 的最大个数。

解题思路

采用滑动窗口的策略，维持一个窗口内最多有 k 个 0。
- 初始化左指针 left、右指针 right 均为 0，同时记录窗口内 0 的个数 zero 为 0。
- 右指针 right 不断向右移动，每碰到一个 0，就将 zero 加 1。
- 当 zero 超过 k 时，说明窗口内 0 的数量过多，需要移动左指针 left，若移动的 nums[left] 是 0，则将 zero 减 1。
- 每次移动指针后，更新连续 1 的最大长度，即 ret = max(ret, right - left + 1)。

代码实现（C++）

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret;
        for(int left=0,right=0,zero=0;right<nums.size();right++)
        {
            if(nums[right]==0)zero++;
            while(zero>k)if(nums[left++]==0)zero--;
            ret=max(ret,right-left+1);
        }
        return ret;
    }
};

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

题目描述

给定一个字符串 s，需要找出其中不包含重复字符的最长子串的长度。

解题思路

运用滑动窗口结合哈希表的方式。
- 初始化左指针 left、右指针 right 为 0，使用一个大小为 128 的数组 hash 来记录字符出现的次数（基于字符的 ASCII 码范围），n 为字符串的长度，temp 用于记录最长子串的长度。
- 右指针 right 向右移动，将 s[right] 字符的出现次数加 1。
- 如果 s[right] 字符的出现次数大于 1，意味着窗口内有重复字符，此时移动左指针 left，并将 s[left] 字符的出现次数减 1。
- 每次移动指针后，更新最长子串的长度，即 temp = max(temp, right - left + 1)。

代码实现（C++）

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int left=0,right=0;
        int hash[128]={0};
        int n=s.size(),temp=0;

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

三、1658. 将 x 减到 0 的最小操作数

题目描述

给定一个整数数组 nums 和一个整数 x。每次操作需要移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。如果能够将 x 恰好减到 0，返回最小的操作数；否则，返回 -1。

解题思路

本题的关键在于转化为寻找数组中和为 sum(nums) - x 的最长子数组。
- 首先遍历数组 nums 进行求和得到 add，计算目标值 target = add - x。如果 target < 0 直接返回 -1；如果 target == 0 直接返回数组的长度。
- 初始化左指针 left 和右指针 right 为 0，窗口内元素的和 sum 为 0，ret 用于记录最长子数组的长度。
- 右指针 right 向右移动，将 nums[right] 加入到 sum 中。
- 当 sum 大于 target 时，移动左指针 left，并将 nums[left] 从 sum 中减去。
- 如果 sum 等于 target，更新最长子数组的长度 ret = max(ret, right - left + 1)。
- 最后根据 ret 的值来判断返回结果，如果 ret == -1 说明不存在符合条件的子数组，返回 -1；否则返回数组长度减去 ret。

代码实现（C++）

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int add=0;
        for(auto e:nums)add+=e;
        int target=add-x;
        if(target<0)return -1;
        int ret=-1;
        for(int left=0,right=0,sum=0;right<nums.size();right++)
        {
            sum+=nums[right];
            while(sum>target)
                sum-=nums[left++];
            if(sum==target)
                ret=max(ret,right-left+1);
        }
        if(ret==-1)return -1;
        else return nums.size()-ret;
    }
};

总结

滑动窗口通过动态地调整窗口的左右边界，能够在一次遍历中高效解决众多关于子数组、子字符串的问题。在实际解题的时候，关键在于明确窗口内需要维护的条件，还有怎样依据条件移动窗口的边界。期望通过这三道题目的分享，能助力大家更好地掌握滑动窗口这一重要的算法技巧。后续还会持续分享更多算法题目的解题思路，欢迎一同交流学习！