跳转至

滑动窗口

滑动窗口指的是这样一类问题的求解方法，在数组上通过双指针同向移动而解决的一类问题。其实这样的问题我们可以不必为它们专门命名一个名字，它们的解法其实是很自然的。

使用滑动窗口解决的问题通常是暴力解法的优化，掌握这一类问题最好的办法就是练习，然后思考清楚为什么可以使用滑动窗口。

应用场景：字符串/数组/子序列

滑动窗口使用思路（寻找最长）

  • 核心：左右双指针（L，R）在起始点，R 向右逐位滑动循环

每次滑动过程中如果窗内元素满足条件，R 向右扩大窗口，并更新最优结果；如果不满足条件，L 向右缩小窗口，直到 R 到达结尾

滑动窗口使用思路（寻找最短）

  • 核心：左右双指针（L，R）在起始点，R 向右逐位滑动循环

每次滑动过程中如果窗内元素满足条件，L 向右扩大窗口，并更新最优结果；如果不满足条件，R 向右缩小窗口，直到 R 到达结尾

模板代码

// 最长模板：
初始化 left, right, result, bestResult
while (右指针没有到结尾) {
    窗口扩大，加入 right 对应元素，更新当前 result
    while (result 不满足要求) {
        窗口缩小，移除 left 对应元素， left 右移
    }
    更新最优结果 bestResult
    right++;
}
return bestResult;

// 最短模板：
初始化 left, right, result, bestResult
while (右指针没有到结尾) {
    窗口扩大，加入 right 对应元素，更新当前 result
    while (result 满足要求) {
        更新最优结果 bestResult
        窗口缩小，移除 left 对应元素， left 右移
    }
    right++;
}
return bestResult;

例题（leetcode）

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

 

进阶：

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
func minSubArrayLen(target int, nums []int) int {
    var left, right, sum, minLength int
    for right < len(nums) {
        sum += nums[right]
        for sum >= target {
            if right - left + 1 < minLength || minLength == 0 {
                minLength = right - left + 1
            }
            sum -= nums[left]
            left++
        }
        right++
    }
    return minLength
}

219 存在重复元素 Ⅱ

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

 

 

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105
func containsNearbyDuplicate(nums []int, k int) bool {
    var set map[int]bool
    set = make(map[int]bool)
    for i, num := range nums {
        if i > k {
            delete(set, nums[i - k - 1])
        }

        if set[num] {
            return true
        }
        set[num] = true
    }
    return false
}

643 子数组最大平均数 Ⅰ

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

 

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

 

提示：

  • n == nums.length
  • 1 <= k <= n <= 105
  • -104 <= nums[i] <= 104
func findMaxAverage(nums []int, k int) float64 {
    left := 0
    right := 0
    sum := 0
    var result float64

    for right < len(nums) {
        sum += nums[right]
        // 窗口大小超过 k 移除 left 元素并左移 left
        for right - left + 1 > k {
            sum -= nums[left]
            left++
        }
        // 更新最优结果
        if right - left + 1 == k {
            if result == 0 {
                result = float64(sum) / float64(right - left + 1)
            }
            if float64(sum) / float64(right - left + 1) > result {
                result = float64(sum) / float64(right - left + 1)
            }
        }
        right++
    }
    return result
}

1876 长度为三且个字符不同的子字符串

如果一个字符串不含有任何重复字符，我们称这个字符串为 好 字符串。

给你一个字符串 s ，请你返回 s 中长度为 3 的 好子字符串 的数量。

注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。

子字符串 是一个字符串中连续的字符序列。

 

示例 1：

输入：s = "xyzzaz"
输出：1
解释：总共有 4 个长度为 3 的子字符串："xyz"，"yzz"，"zza" 和 "zaz" 。
唯一的长度为 3 的好子字符串是 "xyz" 。

示例 2：

输入：s = "aababcabc"
输出：4
解释：总共有 7 个长度为 3 的子字符串："aab"，"aba"，"bab"，"abc"，"bca"，"cab" 和 "abc" 。
好子字符串包括 "abc"，"bca"，"cab" 和 "abc" 。

 

提示：

  • 1 <= s.length <= 100
  • s 只包含小写英文字母。
func countGoodSubstrings(s string) int {
    var (
        left int = 0
        right int = 2
        result int = 0
    )

    if len(s) < 3 {
        return result
    }

    for right < len(s) {
        if isNice(s[left:right + 1]) {
            result++
        }
        left++
        right++
    }
    return result
}

func isNice(s string) bool {
    set := map[rune]bool{}
    for _, value := range s[:] {
        if set[value] {
            return false
        }
        set[value] = true
    }
    return true
}

1984 学生分数的最小差值

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。

返回可能的 最小差值 。

 

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：

输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

 

提示：

  • 1 <= k <= nums.length <= 1000
  • 0 <= nums[i] <= 105
func minimumDifference(nums []int, k int) int {
    min := 0
    temp := 0
    sort.Ints(nums)
    for i := k - 1; i < len(nums); i++ {
        temp = nums[i] - nums[i - k + 1]
        if min == 0 ||  temp < min {
            min = temp
        }
    }
    return min
}

2269 找到一个数字的 K 美丽值

一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：

  • 子字符串长度为 k 。
  • 子字符串能整除 num 。

给你整数 num 和 k ，请你返回 num 的 k 美丽值。

注意：

  • 允许有 前缀 0 。
  • 0 不能整除任何值。

一个 子字符串 是一个字符串里的连续一段字符序列。

 

示例 1：

输入：num = 240, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "240" 中的 "24" ：24 能整除 240 。
- "240" 中的 "40" ：40 能整除 240 。
所以，k 美丽值为 2 。

示例 2：

输入：num = 430043, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "430043" 中的 "43" ：43 能整除 430043 。
- "430043" 中的 "30" ：30 不能整除 430043 。
- "430043" 中的 "00" ：0 不能整除 430043 。
- "430043" 中的 "04" ：4 不能整除 430043 。
- "430043" 中的 "43" ：43 能整除 430043 。
所以，k 美丽值为 2 。

 

提示：

  • 1 <= num <= 109
  • 1 <= k <= num.length （将 num 视为字符串）
func divisorSubstrings(num int, k int) int {
    result := 0
    s := strconv.Itoa(num)
    for i := k - 1; i < len(s); i++ {
        i2, _ := strconv.Atoi(s[i-k+1 : i+1])
        if i2 != 0 && num % i2 == 0 {
            result++
        }
    }
    return result
}

22379 得到 k 个黑块的最少涂色次数

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

 

示例 1：

输入：blocks = "WBBWWBBWBW", k = 7
输出：3
解释：
一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

示例 2：

输入：blocks = "WBWBBBW", k = 2
输出：0
解释：
不需要任何操作，因为已经有 2 个连续的黑块。
所以我们返回 0 。

 

提示：

  • n == blocks.length
  • 1 <= n <= 100
  • blocks[i] 要么是 'W' ，要么是 'B' 。
  • 1 <= k <= n
func minimumRecolors(blocks string, k int) int {
    var left, right, max, pl, pr, result int
    for right < len(blocks) {
        // 记录窗口中黑块数量
        if blocks[right] == 'B' {
            max++
        }
        if right - left + 1 == k {
            // 如果满足条件,记录窗口坐标
            if result == 0 || result < max {
                result = max
                pl = left
                pr = right
            }

            // 判断 left 移动前是否为 'B',因为下一次移动会减去窗口左边的黑块
            if blocks[left] == 'B' {
                max--
            }
            left++
        }

        // 窗口滑动
        right++
    }
    return pr - pl + 1 - result
}

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 由英文字母、数字、符号和空格组成
func lengthOfLongestSubstring(s string) int {
    if len(s) == 1 {
        return 1
    }

    var left, right, result int
    for right < len(s) {
        if left < right {
            // 判断是否满足条件
            for i := right - 1; i >= left; i-- {
                if s[right] == s[i] {
                    left = i + 1
                    break
                }
            }
            // 更新最新结果
            if right-left+1 > result {
                result = right - left + 1
            }
        }
        // 窗口扩大
        right++
    }
    return result
}