您现在的位置是:首页 >技术教程 >滑动窗口算法网站首页技术教程

滑动窗口算法

冷兮雪 2024-06-17 10:19:37
简介滑动窗口算法

目录

滑动窗口算法

基本思想

 可解决问题

应用

题目一:最小覆盖子串

题目解读:

 代码

题目二:长度最小的子数组

题目解读

代码

滑动算法窗口的优缺点

优点:

缺点:


滑动窗口算法

首先介绍一下什么是滑动窗口:滑动窗口算法是一种在数组或字符串中寻找特定模式的算法,它可以在 O(n) 的时间复杂度内解决一些字符串或数组相关的问题。

基本思想

滑动窗口算法的基本思想是维护一个窗口,窗口内是需要处理的数据,每次移动窗口时,我们只需要计算新窗口与旧窗口的区别即可,这样可以大大减少计算量。

具体地说,滑动窗口算法通常包括以下几个步骤:

  1. 初始化左右指针,表示窗口的左右边界。

  2. 移动右指针,扩大窗口,直到找到符合条件的窗口。

  3. 移动左指针,缩小窗口大小,直到不能再缩小为止。

  4. 在窗口移动的过程中,记录窗口的状态,例如最大值、最小值、子串长度等等。

  5. 返回窗口记录的结果。

 可解决问题

滑动窗口算法可以用于解决一些数组和字符串相关的问题,例如:

1. 找到最长的连续子数组或子字符串:可以使用滑动窗口算法来寻找最长的连续子数组或子字符串。在遍历数组或字符串时,我们可以维护一个窗口,通过移动窗口来寻找最长的连续子数组或子字符串。

2. 找到满足某些条件的子数组或子字符串:可以使用滑动窗口算法来寻找满足某些条件的子数组或子字符串。在遍历数组或字符串时,我们可以维护一个窗口,通过移动窗口来寻找满足某些条件的子数组或子字符串。

3. 找到最小的覆盖子串:可以使用滑动窗口算法来寻找最小的覆盖子串。在遍历字符串时,我们可以维护一个窗口,通过移动窗口来寻找最小的覆盖子串。

4. 找到无重复字符的最长子串:可以使用滑动窗口算法来寻找无重复字符的最长子串。在遍历字符串时,我们可以维护一个窗口,通过移动窗口来寻找无重复字符的最长子串。

滑动窗口算法通常适用于处理数组和字符串问题,而且要求问题可以通过窗口内的元素来计算得出。此外,滑动窗口算法通常可以将时间复杂度优化到线性,因此在处理大规模数据时具有很好的效率。

应用

下面,我将通过两道简单题目来演示滑动窗口算法的应用。

题目一:最小覆盖子串

给定两个字符串 S 和 T,求 S 中包含 T 所有字符的最短子串。

示例:

输入:S = "ADOBECODEBANC",   T = "ABC"

输出:"BANC"

题目解读:

我们可以维护两个指针 left 和 right,表示当前窗口的左右边界。初始时,左指针和右指针都指向字符串 S 的第一个字符。我们先移动右指针,直到找到包含字符串 T 的所有字符的子串。然后,我们移动左指针,缩小窗口大小,直到不能再缩小为止。在这个过程中,我们记录窗口的最小长度,并记录最小子串的起始位置。最后返回最小子串。

 代码

public String minWindow(String s, String t) {
    int[] hash = new int[256];//ASCII 字符集共包含256个字符,因此使用长度为256的数组来记录窗口中每个字符出现的次数。
    for (char c : t.toCharArray()) {
        hash[c]++;
    }

    int left = 0, right = 0, count = t.length(), start = 0, len = Integer.MAX_VALUE;
    while (right < s.length()) {
        if (hash[s.charAt(right)] > 0) {
            count--;
        }
        hash[s.charAt(right)]--;
        right++;

        while (count == 0) {
            if (right - left < len) {
                len = right - left;
                start = left;
            }
            if (hash[s.charAt(left)] == 0) {
                count++;
            }
            hash[s.charAt(left)]++;
            left++;
        }
    }
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}

题目二:长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target,找出该数组中满足其和 ≥ target 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。

示例:

输入:nums = [2,3,1,2,4,3], target = 7

输出:2

题目解读

我们可以维护两个指针 left 和 right,表示当前窗口的左右边界。初始时,左指针和右指针都指向数组的第一个元素。我们先移动右指针,直到窗口内的元素之和大于等于 target。然后,我们移动左指针,缩小窗口大小,直到不能再缩小为止。在这个过程中,我们记录窗口的最小长度,并更新最小长度的值。最后,返回最小长度。

代码

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, right = 0, sum = 0, len = Integer.MAX_VALUE;
    while (right < nums.length) {
        sum += nums[right];
        while (sum >= target) {
            len = Math.min(len, right - left + 1);
            sum -= nums[left];
            left++;
        }
        right++;
    }
    return len == Integer.MAX_VALUE ? 0 : len;
}

滑动算法窗口的优缺点

优点:

  1. 时间复杂度较低:滑动窗口算法的时间复杂度通常是O(n),因为它只需要遍历一次原数组。
  2. 空间复杂度较低:滑动窗口算法通常只需要使用常数级别的额外空间。
  3. 简单易懂:滑动窗口算法的思路比较简单,容易理解和实现。

缺点:

  1. 无法解决所有子串问题:滑动窗口算法只适用于解决一些特定类型的子串问题,无法解决所有子串问题。
  2. 可能存在重复计算:在一些情况下,滑动窗口算法可能会对同一段区间进行重复计算,导致效率降低。
  3. 可能存在局限性:滑动窗口算法有些场景下可能无法得到最优解,需要结合其他算法进行优化。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。