趣味算法：滑动窗口算法的理解与应用_为什么利用滑动窗口就可以将输入变成t-2个子序列_如何理解滑动窗口

先自我介绍一下，小编浙江大学毕业，去过华为、字节跳动等大厂，目前阿里P7

深知大多数程序员，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新Linux运维全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上运维知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

如果你需要这些资料，可以添加V获取：vip1024b （备注运维）

正文

文章目录

• 前言
• • 一、滑动窗口算法简介
    • 二、滑动窗口算法的应用场景
    • 三、滑动窗口算法的基本步骤
    • 四、滑动窗口算法实践
    • • 1. 数组中的最大/最小子序列问题：最大连续子数组和
        • 2. 固定长度的子序列问题：长度为K的无重复字符子串
        • 3. 计数类问题：子数组和等于K的数量
    • 五、滑动窗口与其他算法的比较
    • 六、总结

前言

在编程和数据结构中，滑动窗口算法是一种常见的解决问题的方法。它主要用于处理涉及连续或固定长度子数组、子序列或子字符串的问题。本文将深入探讨滑动窗口算法，包括其基本概念、应用场景、基本步骤以及具体的Java代码实践。

一、滑动窗口算法简介

滑动窗口算法是一种优化技巧，主要用于解决数组或链表中的子序列或子串问题。其主要优势是能够将一些复杂问题的时间复杂度降低至线性。

二、滑动窗口算法的应用场景

滑动窗口算法有广泛的应用场景，它通常用于解决涉及连续或固定长度子数组、子序列或子字符串的问题。以下是一些具体的例子：

• 数组中的最大/最小子序列问题：例如，“最大连续子数组和”，“最小覆盖子串”等。这些问题通常需要找出数组或字符串中的一段连续子区间，使其满足某种条件（如和最大或最小，或者包含所有指定字符等）。
• 固定长度的子序列问题：例如，“长度为K的无重复字符子串”，“和为K的连续子数组”等。这些问题通常需要找出长度固定或变动的子序列，满足特定的条件。
• 计数类问题：例如，“和为K的子数组个数”，“所有字母异位词”等。这类问题需要统计满足特定条件的子数组或子字符串的数量。

滑动窗口算法的强大之处在于，它可以将这些看似复杂的问题转化为线性复杂度，大大提高了算法的运行效率。在理解了滑动窗口的基本原理后，我们可以灵活地应用它来解决各种各样的问题。

三、滑动窗口算法的基本步骤

滑动窗口算法通常涉及以下几个核心步骤：

1. 初始化一个窗口：窗口通常表示为数组或字符串中的一段连续子区间，可以用两个指针（例如left和right）来表示其边界。初始时，这个窗口可以是空的，或者包含一个或多个元素。
2. 移动窗口：根据具体的问题，可能需要向右移动窗口的左边界（缩小窗口），或者向右移动窗口的

右边界（扩大窗口）。窗口的移动会改变窗口中的元素。

3. 根据窗口的变化更新结果：每次移动窗口时，都需要根据窗口中的新元素和/或去掉的元素来更新需要计算的结果。例如，如果需要计算窗口中的元素之和，当窗口增加一个元素时，需要将这个元素加到总和中；当窗口去掉一个元素时，需要将这个元素从总和中减去。

通过不断移动窗口并更新结果，我们可以在遍历一次数组或字符串后得到问题的解。

四、滑动窗口算法实践

让我们通过以下几个具体的例子，来深入理解如何在实际问题中应用滑动窗口算法。

1. 数组中的最大/最小子序列问题：最大连续子数组和

问题描述：给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

Java解决方案：

public int maxSubArray(int[] nums) {
    int n = nums.length;
    // 初始化当前子数组的和为第一个元素的值，最大和也为第一个元素的值
    int curr_sum = nums[0], max_sum = nums[0];

    // 从第二个元素开始遍历数组
    for(int i = 1; i < n; ++i) {
        // 更新当前和，取当前元素与（当前和+当前元素）中的最大值
        curr_sum = Math.max(nums[i], curr_sum + nums[i]);
        // 更新最大和，取当前最大和与当前和中的最大值
        max_sum = Math.max(max_sum, curr_sum);
    }
    // 返回最大和
    return max_sum;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码解析：

上述代码中，curr_sum 是用来保存当前子数组的和，max_sum 用来保存最大的子数组和。初始化都为第一个元素。

当我们从第二个元素开始遍历数组时，对于每个元素，我们有两种选择，要么将它加入到当前的子数组中，要么开始一个新的子数组（即该元素自己成为一个新的子数组）。这取决于 curr_sum + nums[i] 和 nums[i] 之间的大小关系，我们用 Math.max(nums[i], curr_sum + nums[i]) 来判断，选择较大者作为新的 curr_sum。

同时，我们也需要更新 max_sum，也就是最大子数组和。通过 Math.max(max_sum, curr_sum) 来实现，即选择 max_sum 和 curr_sum 中较大者作为新的 max_sum。

最后返回的 max_sum 就是最大的子数组和。

2. 固定长度的子序列问题：长度为K的无重复字符子串

问题描述：给定一个字符串 s，找出该字符串中长度为 K 的无重复字符子串的数量。

Java解决方案：

public int numKLenSubstrNoRepeats(String s, int K) {
    // 计数数组，用于记录字符出现的次数
    int[] count = new int[26];
    int res = 0;
    // 双指针遍历字符串
    for (int i = 0, j = 0; j < s.length(); j++) {
        // 当前字符出现次数加1，如果这是第一次出现，则K减1
        if (count[s.charAt(j) - 'a']++ == 0) K--;
        // 如果K小于0，说明窗口太大，需要移动左指针缩小窗口
        if (K < 0 && count[s.charAt(i++) - 'a']-- == 1) K++;
        // 如果K等于0，说明找到了一个满足条件的子串，结果加1
        if (K == 0) res++;
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码解析：

在此代码中，我们定义了一个 count 数组，用来统计各字符在滑动窗口中出现的次数。同时定义了两个指针 i 和 j ，分别表示窗口的左右边界。

我们从左到右滑动 j 指针（即遍历字符串）。如果遍历到

的字符第一次出现，那么 K 就减一。当 K 小于0时，说明窗口太大了，有字符重复出现，需要移动左指针 i 缩小窗口，直到 K 大于等于0。在移动 i 的过程中，我们需要将离开窗口的字符的次数减一，如果这个字符的次数变为0，那么 K 就增加一。每次当 K 为0时，我们就找到了一个长度为 K 的无重复字符子串，res 就加一。

最后的话

最近很多小伙伴找我要Linux学习资料，于是我翻箱倒柜，整理了一些优质资源，涵盖视频、电子书、PPT等共享给大家！

资料预览

给大家整理的视频资料：

给大家整理的电子书资料：

如果本文对你有帮助，欢迎点赞、收藏、转发给朋友，让我有持续创作的动力！

网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。

需要这份系统化的资料的朋友，可以添加V获取：vip1024b （备注运维）

一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
么很难做到真正的技术提升。**

需要这份系统化的资料的朋友，可以添加V获取：vip1024b （备注运维）
[外链图片转存中…(img-eMTUt6Qi-1713657893548)]

一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！