滑动窗口(一)

2023-12-18 23:38:42

滑动窗口

什么是滑动窗口算法?通俗的来讲就是 “同向双指针” ,当一组数据的规律含有单调性的时候,就可以使用下面这套逻辑来优化暴力解法。

当两个指针同向移动的时候,类似于一个窗口在滑动。使用于在连续序列里找特殊的子串、子数列、子数组等。

下面将用一道题来解释上面的逻辑。

长度最小的子数组

长度最小的子数组?

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

找出该数组中满足其和?≥ target?的长度最小的?连续子数组?[numsl, numsl+1, ..., numsr-1, numsr]?,并返回其长度如果不存在符合条件的子数组,返回?0?。

定义两个指针 left,right,都从零位置开始,用 sum 记录子数组的和。

第一步:进窗口(sum+=nums [right] ),将第一个值添加到 sum 中。

第二步:判断:sum 是否 大于等于题目要求的 target ,如果符合,就进入循环:更新长度 最小长度 len,让‘窗口’向右划(left左移)!再次进行第二步的判断,当不满足 sum 大于等于 target 这个要求的时候,就让 right++,准备下次的进窗口。

这道题还有一个细节需要注意:需要定义一个 flag 如果 满足过sum大于等于?就要让 flag 的值改变,只要当他满足过的时候,才能返回 len,否则就是序列中没有满足条件的,返回 0。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, n = nums.size();
        int sum = 0;
        int len = nums.size();
        int flag = 0;
        while (right < n)
        {    
            sum += nums[right];
            while(sum >= target)
            {
                flag = 1;
                if (right - left < len) len = right - left + 1;
                sum -= nums[left];
                left++;
            }
            right++;
        }
        if(flag == 1) return len;
        else return 0;
    }
};

无重复字符的最长子串?

无重复字符的最长子串

给定一个字符串?s?,请你找出其中不含有重复字符的?最长连续子字符串?的长度。

思路:利用哈希表作为判断字符是否重复的依据,使用滑动窗口更新最长的长度。

因为数据比较少,所以可以直接使用 ASCII 来构建哈希表,将ASCII 当做下标,出现了的话那个位置的数就加1.

判断条件为:hash 表里 right 位置的值大于1,说明有重复的字符进入了哈希表,然后开始出窗口,循环出,直至这个 hash 表里 right 位置的值等于1后,right++,为下一次进窗口做准备。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0,right = 0,n=s.size();
        int len = 0;
        int hash[128]={0};
        while(right < n)
        {
            hash[s[right]]++;
            while(hash[s[right]]>1)
            {
                hash[s[left++]]--;
            }
            len = max(len, right -left + 1);
            right++;
        }
        return len;
    }
};

最大连续1的个数?

最大连续1的个数 III

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

此题如果采用正常方法的话,将是特别特别难的一道题,所以采用正难则反的思想。

将题目中找反转不大于K个0后的连续1的最大个数,转化为:找最长的子数组,其中这个子数组中 0 的个数不大于 K,利用滑动指针来解决就可以了,判断条件就是子数组中 0 个数小于等于 K,更新的结果就是这个子数组的长度!

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        //题目转化为在数组中找到一个子数组,里面零的个数小于 K 个
        int left = 0, right = 0, zero = 0;
        int n = nums.size();
        int len = 0;
        while (right < n)
        {
            if(nums[right]==0) zero++;
            while (zero > k)
            {
                if (nums[left] == 0) zero--;
                left++;
            }
            len = max(len, right - left+1);
            right++;
        }
        return len;
    }
};

将 x 减到 0 的最小操作数?

?将 x 减到 0 的最小操作数

给你一个整数数组?nums?和一个整数?x?。每一次操作时,你应当移除数组?nums?最左边或最右边的元素,然后从?x?中减去该元素的值。请注意,需要?修改?数组以供接下来的操作使用。

如果可以将?x?恰好?减到?0?,返回?最小操作数?;否则,返回?-1?。

依旧是正难则反

将问题转化为:在数组中间找到一个最长的子数组,使它的值恰好等于 sum - x,?当数组中间这个子数组最长时,刚好对应了两边的数(即操作最少),算出除了这个数组外序列剩余的个数,就找到了最小操作数。

文章来源:https://blog.csdn.net/zyb___/article/details/135071370
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。