做冷库的网站,广告设计与制作属于什么专业类别,wordpress新闻类主题,网页设计的发展什么是滑动窗口#xff1f;
滑动窗口是算法中一种非常有用的技术#xff0c;特别是在处理数据序列或数组时。它的核心思想是维护一个固定大小的窗口#xff0c;这个窗口在数据序列上滑动#xff0c;以便于在窗口内的元素上进行操作或计算。滑动窗口技术通常用于解决与数据…什么是滑动窗口
滑动窗口是算法中一种非常有用的技术特别是在处理数据序列或数组时。它的核心思想是维护一个固定大小的窗口这个窗口在数据序列上滑动以便于在窗口内的元素上进行操作或计算。滑动窗口技术通常用于解决与数据子序列相关的问题例如
最大子数组和找到数组中和最大的连续子数组。最小覆盖子串找到覆盖所有字符的最短子串。最长不重复子串找到最长的不包含重复字符的连续子串。
滑动窗口的基本操作
初始化设置窗口的起始和结束位置通常起始位置 start 和结束位置 end 都初始化为 0。扩展窗口将窗口的结束位置 end 向右移动即 end以包含更多的元素。收缩窗口如果窗口的大小超出了限制或者不再满足特定的条件例如需要保持窗口内元素的和不超过某个值则将窗口的起始位置 start 向右移动即 start以排除窗口左侧的元素。
滑动窗口的实现步骤
初始化设置窗口的起始和结束索引以及可能需要的辅助数据结构如哈希表、队列等。计算窗口值根据问题需求计算窗口内元素的和、最大值、最小值等。滑动窗口根据窗口内的条件决定是扩展窗口还是收缩窗口。 如果窗口大小未达到要求扩展窗口。如果窗口大小达到要求但满足条件记录结果然后扩展窗口。如果窗口大小达到要求但不满足条件收缩窗口。更新结果在每次窗口滑动后根据问题需求更新全局结果。
示例最长不重复子串
假设我们要找到字符串中最长的不包含重复字符的子串。使用滑动窗口的方法我们可以这样做
使用一个哈希表来记录窗口内字符的出现次数。使用两个指针表示窗口的起始和结束位置。遍历字符串将遇到的字符加入哈希表并扩展窗口。如果哈希表中字符的总数超过了窗口大小说明有重复字符需要收缩窗口。在每次窗口滑动后更新最长不重复子串的长度。
滑动窗口技术是一种非常灵活的方法可以根据不同的算法问题进行调整和优化。
示例题目
解题思路
这段代码是一个 JavaScript 函数用于解决一个典型的滑动窗口问题找到数组中和至少为 target 的最短子数组的长度。下面是这个函数的解题思路 初始化变量 start 和 end 分别表示滑动窗口的起始和结束位置初始时都设置为 0。len 存储数组 nums 的长度。res 用来存储最短子数组的长度初始值设为 Infinity表示无穷大因为我们要找到最短的长度。sum 用来存储当前窗口内所有元素的和初始值为 0。 外层循环 使用 while 循环条件是 end len确保 end 索引不会超出数组长度。 扩展窗口 在每次循环中将 end 索引对应的元素加到 sum 上扩展窗口。 检查窗口和 使用内层 while 循环检查当前窗口的和是否大于 target。如果 sum 大于 target则需要收缩窗口。 收缩窗口 如果 sum 大于 target则更新 res 为当前窗口长度 end - start 的最小值。然后从 sum 中减去 start 索引对应的元素并将 start 向右移动一位从而收缩窗口。 更新结束索引 无论是否收缩窗口外层循环的每次迭代结束时都将 end 向右移动一位。 处理边界情况 在循环结束后如果 res 仍然是 Infinity说明没有找到任何满足条件的子数组此时返回 0。如果找到了满足条件的子数组返回 res 的值。 返回结果 使用三元运算符检查 res 是否为 Infinity如果是则返回 0否则返回 res。
这个函数的时间复杂度是 O(n)其中 n 是数组 nums 的长度因为每个元素最多被访问两次一次添加到 sum一次从 sum 中减去。空间复杂度是 O(1)因为我们只使用了固定数量的额外变量。
答案
总结
滑动窗口是一种强大的算法工具能够以线性时间解决多种子数组相关问题是算法竞赛和工业界中常用的技术之一
