首页 > 编程语言 >滑动窗口算法专题(1)

滑动窗口算法专题(1)

时间:2024-09-22 09:51:14浏览次数:10  
标签:专题 nums int len ++ 算法 right 滑动 left

找往期文章包括但不限于本期文章中不懂的知识点:

个人主页:我要学编程(ಥ_ಥ)-CSDN博客

所属专栏: 优选算法专题

目录

滑动窗口算法的简介

209. 长度最小的子数组

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

1004. 最大连续1的个数III

1658. 将×减到0的最小操作数


滑动窗口算法的简介

滑动窗口算法本质上就是双指针算法的一个衍生版本。

这个就是类似双指针算法里的快慢指针。但是快慢指针一般用去求序列的长度或是中间位置等问题,且快慢指针的速度一般都是固定的。但是滑动窗口算法中的 left指针和 right指针移动是根据题目的要求进行的。

滑动窗口算法的步骤也是固定的,即有自己固定的套路。一般步骤如下:

1、初始化窗口:left = 0,right = 0;

2、 扩大窗口:right++;

3、判断题目的要求。

接下来就是根据 第三步的结果来进行不同的处理。

如果满足题目要求,就继续扩大窗口的大小,再进行判断。即重复2、3步骤。如果不满足题目要求就得更新结果,再缩小窗口,接着再去判断是否满足题目要求,即循环判断是否满足题目要求。

滑动窗口算法广泛应用于数组和字符串等序列中求子序列的问题。例如:求子数组、子字符串等。

上面就是简介的全部了。

下面就开始实战。

209. 长度最小的子数组

题目: 

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

找出该数组中满足其总和大于等于 target 的长度最小的子数组(可以去原题看解释)

  [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度 如果不存在符合条件的子数组,返回  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 <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

思路: 首先想到的就是去遍历数组,找出不同的长度,然后比较找出最小值即可。

最暴力的解法就是枚举每一个数组元素的对应长度的值,最终最短的路径一定是在这些值里面的。

代码实现:

错误解法(暴力枚举):

class Solution {
    // 暴力枚举
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int right = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int left = 0;
        while (right < nums.length) {
            // 首先得计算sum的值
            sum += nums[right];
            // 再判断sum 和 target的大小关系
            if (sum < target) {
                right++;
            } else {
                // 将长度,入堆,再继续往后走
                minHeap.add(right-left+1);
                right = ++left;
                sum = 0;
            }
        }
        // 小根堆可能为空,得判断
        return minHeap.isEmpty() == true ? 0 : minHeap.peek();
    }
}

上面代码去运行时,会超出时间限制。但是有一个让我很疑惑的地方。如下所示:

我个人认为是这个后台在跑一个测试用例时,能通过;但是全部一起跑的时候,最终的叠加时间超出了时间限制。 

接下来就得开始进行优化。上面的代码有一个地方时发生了重复计算的:当我们找出符合条件的子区间时,不应该从头继续开始,我们上面的做法是跳过left所在的元素,继续往后遍历寻找。但是有一个更优的方法:直接让left++不就行了吗。这就节约了继续跑的时间。

但有小伙伴可能会疑惑:有没有可能漏掉了值呢?答案是不可能的。现在right所在的位置是上一次满足条件的位置,并且这个位置是加上left才满足的,因此去掉left之后,在[left+1,right)的位置肯定不会满足条件的。因此我们可以大胆的去做。

但是可能在去掉 left 之后,还可能继续大于 target,因此这里我们可以加上一个循环判断直至小于target。

优化解法: 

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        while (right < nums.length) {
            sum += nums[right];
            // 满足条件,就一直更新并缩小窗口
            while (sum >= target) {
                minHeap.add(right-left+1);
                sum -= nums[left++];
            }
            // 走到这里说明sum < target
            right++;
        }
        return minHeap.isEmpty() ? 0 : minHeap.peek();
    }
}

上面的代码的效率还不是最优,因为我们使用堆这个数据结构来存储和计算最小长度。这个时间可不能忽略。因此下面就是不使用堆的做法。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        // 这里不能是0,求最小值时会有影响
        int len = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right];
            // 满足条件,就一直更新并缩小窗口
            while (sum >= target) {
                len = Math.min(len, right-left+1);
                sum -= nums[left++];
            }
            // 走到这里说明sum < target
            right++;
        }
        // 可能while循环没进入,len的值还是int最大值
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

下面就来分析一下,滑动窗口的做法:

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 * 104
  • s 由英文字母、数字、符号和空格组成

思路: 这里要我们找不重复的最长子串。首先看到不重复,我们就应该想到用哈希表来解决。那么这里的暴力枚举思路也就出来了。直接遍历字符串,找到一个字符,看其是否在哈希表中。如果在,则从下一个位置开始遍历;反之,则将其加入哈希表,继续往后遍历。

代码实现: 

暴力枚举版本(能通过,但效率低下):

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        Map<Character, Integer> hash = new HashMap<>();
        int count = 0;
        int len = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            // 看哈希表中是否出现过这个元素
            if (hash.getOrDefault(ch, 0) == 0) {
                // 没出现就添加,再继续遍历
                hash.put(ch, 1);
                right++;
                count++;
            } else {
                // 记录最长子串的长度,并更行count
                len = Math.max(count, len);
                count = 0;
                // right从头开始,哈希表中的元素也得清除
                right = ++left;
                hash.clear();
            }
        }
        // 可能出现没有重复的现象或者未被更新
        len = Math.max(count, len);
        return len;
    }
}

 这个代码的思想总体上和上一题的暴力枚举是一样的。出现了重复的字符,就从left+1的位置继续开始遍历。上一题在处理这种情况时,是我们了解了在right位置之前不会出现这种情况,所以我们可以直接让left++。但是在这里即使left++了也不一定能跳过重复的字符。

优化后的版本: 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        Map<Character, Integer> hash = new HashMap<>();
        int count = 0;
        int len = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            // 看哈希表中是否出现过这个元素
            if (hash.getOrDefault(ch, 0) == 0) {
                // 没出现就添加,再继续遍历
                hash.put(ch, 1);
                right++;
                count++;
            } else {
                // 判断是否还有重复的元素
                while (hash.getOrDefault(ch, 0) != 0) {
                    len = Math.max(len, count); // 更新长度
                    hash.remove(ch); // 删除元素(不一定是重复的)
                    count--; // 计数器--
                    ch = s.charAt(left++); // 遍历找寻重复的元素
                }
            }
        }
        // 同样也可能全部是不重复的
        len = Math.max(len, count);
        return len;
    }
}

 但这个还不是最优的版本。由于我们使用了哈希表这个数据结构,在查询和删除时,都需要浪费一些时间。因此最优的版本就是使用数组来模拟哈希表。

最优版本:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        int[] hash = new int[128]; // 根据ASCII码表来指定
        int count = 0;
        int len = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            // 看哈希表中是否出现过这个元素
            if (hash[ch] == 0) {
                // 没出现就添加,再继续遍历
                hash[ch]++;
                right++;
                count++;
            } else {
                // 判断是否还有重复的元素
                while (hash[ch] != 0) {
                    len = Math.max(len, count); // 更新长度
                    hash[ch]--; // 删除元素(不一定是重复的)
                    count--; // 计数器--
                    ch = s.charAt(left++); // 遍历找寻重复的元素
                }
            }
        }
        // 同样也可能全部是不重复的
        len = Math.max(len, count);
        return len;
    }
}

这个最优版本就是用数组模拟实现了哈希表而已,并没有其他的多余变化。 

从这里我们也可以得出一个结论:能够自己手动的模拟实现该数据结构的功能,尽量可以手动实现,这不仅可以提升时间效率,而且在面试的时候,还能让面试官对我们另眼相看。

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 <= 105
  • nums[i] 不是 0 就是 1
  • 0 <= k <= nums.length

注意:这个题目一定不能去修改对应位置为1,那样根本就解不出来。此次修改对应位置的值之后,拿下一次还得还原并且将另外的位置进行修改。因此这种修改对应位置的题目,一般是采用一个计数器来进行逻辑修改,从而实现最终的解题。 

思路:题目的要求就是让我们找到数组中连续1的最大长度。即在序列中寻找符合要求的子序列。这就是用滑动窗口算法来解决。首先考虑暴力枚举的方法。从 left 为0的位置开始往后遍历,遇到1,right++,遇到0,计数器++。当计数器的长度等于k时,就得停下来了,计算此时序列的长度。然后再从left+1的位置开始继续遍历,直至序列遍历完成。接下来就要去优化了。如下所示:

代码实现:

这里就不再给出暴力枚举的代码,大家可以自行实现(参照上面的暴力枚举):

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int right = 0;
        int len = 0;
        int count = 0;
        while (right < nums.length) {
            if (nums[right] == 1) { // 继续走
                right++;
            } else { // 判断0的个数是否符合要求
                if (count < k) {
                    count++;
                    right++; // 还能继续走
                } else {
                    // 此时right的位置并非合法位置
                    len = Math.max(len, right-left);
                    while (nums[left] == 1) { // 要跳过0
                        left++;
                    }
                    // 此时left对应的位置为0
                    left++;
                    count--;
                }
            }
        }
        // 可能会出现没有统计len的情况,即count<k一直满足
        len = Math.max(len, right-left);
        return len;
    }
}

1658. 将×减到0的最小操作数

题目:

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

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

示例 1:

输入:nums = [1,1,4,2,3], x = 5
输出:2
解释:最佳解决方案是移除后两个元素,将 x 减到 0 。

示例 2:

输入:nums = [5,6,7,8,9], x = 4
输出:-1

示例 3:

输入:nums = [3,2,20,1,1,3], x = 10
输出:5
解释:最佳解决方案是移除后三个元素和前两个元素(总共 5 次操作),将 x 减到 0 。

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104
  • 1 <= x <= 109

思路:读完题,如果从正面直接去写,根本没有丝毫的思路。从上面给的示例也可以看出:左边突然使用一下,接着又是右边突然使用一下,这根本没有任何的规律和逻辑。因此我们得从反面来写,题目是让我们找出长度最小的一段或者多段连续的序列的和刚好等于x(序列必须来自最左边或者最右边)。我们完全可以按照下面的方式来处理:

因此,这里题目就转换成了寻找一段连续的最长的序列其和的值为sum-x即可。这里就是用到滑动窗口的算法步骤来解决。

代码实现:

class Solution {
    public int minOperations(int[] nums, int x) {
        // 计算出要寻找的目标值
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        int target = sum - x;
        // 当target小于0时,肯定不可能找到(数组元素全部是大于0的)
        if (target < 0) {
            return -1;
        }
        // 找出最长的序列长度
        int left = 0;
        int right = 0;
        sum = 0;
        int len = -1; // 这里不能是0,可能后面更新的结果是0
        while (right < nums.length) {
            sum += nums[right];
            if (sum < target) {
                right++; // 继续往后寻找
            } else { // sum >= target
                while (sum > target) {
                    sum -= nums[left];
                    left++;
                }
                if (sum == target) {
                    len = Math.max(len, right-left+1); // 记录此时的长度
                }
                // 这里避免死循环造成left越界
                right++;
            }
        }
        // 要么计算出来了值,要么啥也没有
        return len == -1 ? -1 : nums.length-len; 
    }
}

注意:这里len的初始化一定不能是0。因为当len是0,并且target == sum 时,最后就会导致left与right一直是指向同一个位置,即两者算出的长度为0,但是我们最后再判断时,输出的结果是-1;而我们想要的结果是 nums.length。因此这里一定不能初始化为0。

总结:这一题算是这四个题目中最难的一个。思路就不是正常人可以想到的,即使想到了之后,后面的一些细节问题的处理也是需要我们正常人去反复调试对比的,根本不是一次就能AC的。这道题难度还是非常大的。 

好啦!本期 滑动窗口算法专题(1)的学习之旅 就到此结束啦!我们下一期再一起学习吧!

标签:专题,nums,int,len,++,算法,right,滑动,left
From: https://blog.csdn.net/2301_80854132/article/details/142335876

相关文章

  • 水母搜索算法(JS)优化BP神经网络原理及Matlab代码
    目录0引言1数学模型2优化方式3Matlab代码3.1伪代码3.2 JS主函数代码3.2JS-BP4视频讲解0引言水母搜索算法(JellyfishSearch,JS)是由Jui-ShengChou在2020年基于水母搜索行为提出的群智能算法。该算法模拟水母搜索行为的包括它们的洋流跟随,它们在水母群中的运......
  • 水母搜索算法(JS)优化支持向量机原理及Matlab代码
    目录0引言1数学模型2优化方式3Matlab代码3.1伪代码3.2 JS主函数代码3.2JS-SVM4视频讲解0引言水母搜索算法(JellyfishSearch,JS)是由Jui-ShengChou在2020年基于水母搜索行为提出的群智能算法。该算法模拟水母搜索行为的包括它们的洋流跟随,它们在水母群中的运......
  • 水母搜索算法(JS)优化长短期记忆神经网络原理及Matlab代码
    目录0引言1数学模型2优化方式3Matlab代码3.1伪代码3.2 JS主函数代码3.2JS-LSTM4视频讲解0引言水母搜索算法(JellyfishSearch,JS)是由Jui-ShengChou在2020年基于水母搜索行为提出的群智能算法。该算法模拟水母搜索行为的包括它们的洋流跟随,它们在水母群中的......
  • 【多变量输入单步预测】基于减法优化器算法(SABO)优化CNN-BiLSTM-Attention的风电功率
         ......
  • 冒泡排序、选择排序、插入排序 - JavaScript 中的数据结构和算法
    排序算法是许多计算任务的支柱,在组织数据以实现高效访问和处理方面发挥着至关重要的作用。无论您是刚刚开始探索算法世界的初学者,还是希望刷新知识的经验丰富的开发人员,了解这些基本排序技术都是至关重要的。在这篇文章中,我们将探讨一些更基本的排序算法-冒泡排序、选择排序和插......
  • 使用 KMeans 聚类算法 对鸢尾花数据集进行无监督学习的简单示例
    代码功能主要功能:加载数据集:代码使用load_iris()函数加载了鸢尾花数据集(Irisdataset)。这个数据集包含150条样本,每条样本有4个特征,对应于3种不同的鸢尾花。KMeans聚类:使用KMeans聚类算法将样本数据分为3个聚类(即3类),尝试发现数据中的自然分组,而不使用标签......
  • Datawhale Leecode基础算法篇 task02:递归算法and分治算法
    官方学习文档:datawhalechina往期task01:枚举算法链接:DatawhaleLeecode基础算法篇task01:枚举算法递归算法递归简介递归(Recursion):指的是一种通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中,可以通过在函数中再次调用函数自身的方式来实现递归。举......
  • 介绍MPC和LQR算法
    好的,我很乐意为您介绍控制理论中的MPC(模型预测控制)和LQR(线性二次型调节器)算法。MPC(模型预测控制):原理:基于系统模型预测未来输出在预测时域内优化控制序列仅执行当前最优控制,然后重新计算特点:可处理多变量系统和约束能够预见未来变化计算复杂度较高应用:......
  • 【数据结构与算法 | 灵神题单 | 栈基础篇】力扣1441, 844, 682
    1.力扣1441:用栈操作构建数组1.1题目:给你一个数组 target 和一个整数 n。每次迭代,需要从  list={1,2,3...,n} 中依次读取一个数字。请使用下述操作来构建目标数组 target :"Push":从 list 中读取一个新元素,并将其推入数组中。"Pop":删除数组中的最后一......
  • Python基于TensorFlow实现时间序列循环神经网络回归模型(LSTM时间序列回归算法)项目实
    说明:这是一个机器学习实战项目(附带数据+代码+文档+视频讲解),如需数据+代码+文档+视频讲解可以直接到文章最后获取。1.项目背景随着信息技术的发展和传感器设备的广泛应用,时间序列数据的产生量急剧增加。无论是股市价格的波动、电力消耗的趋势还是环境监测的数据变化,准确地预......