【LeetCode 算法专题突破】定长滑动窗口

文章目录

前言

题目会根据顺序，难度逐渐上升。

“那些看似不起波澜的日复一日，会在某天让你看到坚持的意义。”

1456. 定长子串中元音的最大数目

题目描述：难度分1263

代码与解题思路

思路比较简单，这里就不赘述了，之后思路比较简单明了的题目都不会过多分析题目

func maxVowels(s string, k int) int {
    l, r, n, cnt, ans := 0, 0, len(s), 0, 0
    for r < n {
        if check(s[r]) == true {
            cnt++
        }
        if r-l > k-1 { // 定长窗口, 所以可以用 if, 用 for 也行
            if check(s[l]) == true {
                cnt--
            }
            l++
        }
        r++
        ans = max(ans, cnt)
    } 
    return ans
}

func check(s byte) bool {
    return strings.Contains("aeiou", string(s))
}

代码复盘

这段代码有什么可以学习和积累的地方吗？

1、判断函数 check 使用：strings.Contains(“aeiou”, string(s))，巧妙的方式判断一个字符是否在一个字符集合中，以本题为例：用于判断当前字符是否是元音字母

2、定长滑动窗口如何判断是否达到题目要求的长度：if r-l > k-1 表明已经超过了题目要求的长度，可以 ”滑动“ 窗口了

3、每轮循环最后，稳定进行：r++ 和维护最大/最小值的行为

我们带着学习到的知识，继续做下一道题目

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

题目描述：难度分1280

代码与解题思路

func divisorSubstrings(num int, k int) int {
    s := strconv.Itoa(num)
    l, r, ans, n := 0, 0, 0, len(s)
    for r < n {
        t, _ := strconv.Atoi(s[l:r+1])
        if r-l == k-1 && check(num, t) == true { // 达到题目要求之后再 check
            ans++
        }
        if r-l == k-1 { // 在达到长度 k 之后, 每次都进行 l++ 和 r++, 保持前进
            l++
        }
        r++
    }
    return ans
}

func check(num, t int) bool {
    if t == 0 { // t 不能为 0
        return false
    }
    return num%t == 0
}

代码复盘

依旧是使用同一个模板，但有些细节的地方需要注意

1、整数转字符串不能用 string(num) 而需要用 strconv.Itoa(num)

2、根据题目不同的情况和要求，注意判断 l 窗口边界移动的时机

3、使用取模运算的时候，计算的数字不能为 0

1984. 学生分数的最小差值

题目描述：难度分1306

代码与解题思路

题目要求的是 k 个数之间的最高分和最低分的最小差值，在排序之后，让最右边的数 - 最左边的数，得到的就是这个区间最高分和最低分的差值了，再求所有区间的最小值就能求出题目要求的答案了

func minimumDifference(nums []int, k int) int {
    sort.Ints(nums)
    ans := nums[k-1] - nums[0]
    for i := k; i < len(nums); i++ {
        ans = min(ans, nums[i]-nums[i-k+1])
    }
    return ans
}

代码复盘

1、巧妙利用 i 作为滑动窗口右边界，i-k+1 作为滑动窗口左边界

2、对于示例一的特例，通过初始化 ans := nums[k-1] - nums[0] 来解决

643. 子数组最大平均数 I

题目描述：难度分（无）

代码与解题思路

func findMaxAverage(nums []int, k int) float64 {
    l, r, n, sum, ans := 0, 0, len(nums), 0, -math.MaxInt/2
    for r < n {
        sum += nums[r]
        if r-l == k-1 {
            ans = max(ans, sum)
            sum -= nums[l]
            l++
        }
        r++
    }
    return float64(ans)/float64(k)
}

代码复盘

1、使用 -math.MaxInt/2 作为 ans 的初值，既能防止溢出，又能保证他作为最小值

2、巧妙完成题目返回 float64 的要求：直接在最后进行强转 float64(ans)/float64(k)

1343. 大小为 K 且平均值大于等于阈值的子数组数目

题目描述：难度分1317

代码与解题思路

func numOfSubarrays(arr []int, k int, threshold int) (ans int) {
    l, r, n, sum := 0, 0, len(arr), 0
    for r < n {
        sum += arr[r]
        if r-l == k-1 {
            if sum/k >= threshold {
                ans++
            }
            sum -= arr[l]
            l++
        }
        r++
    }
    return ans
}

代码复盘

直接用模板秒了，非常典型

2090. 半径为 k 的子数组平均值

题目描述：难度分1358

代码与解题思路

func getAverages(nums []int, k int) (ans []int) {
    l, r, n, sum := 0, 0, len(nums), 0
    for r < n {
        sum += nums[r]
        ans = append(ans, -1)
        if r-l == k*2 { // 窗口符合题目要求长度
            if k == 0 { // 特判 k = 0 的情况
                ans[r-k] = sum
            } else {
                ans[r-k] = sum/(k*2+1)
            }
            sum -= nums[l]
            l++
        }
        r++
    }
    return ans
}

代码复盘

同样是定长滑动窗口，相比之前的题目稍微灵活了一些，使用自己熟悉的模板，具体情况具体分析即可

2379. 得到 K 个黑块的最少涂色次数

题目描述：难度分1360

代码与解题思路

func minimumRecolors(blocks string, k int) int {
    l, r, n, cnt, ans := 0, 0, len(blocks), 0, math.MaxInt/2
    for r < n {
        if blocks[r] == 'W' {
            cnt++
        }
        if r-l == k-1 {
            ans = min(ans, cnt)
            if blocks[l] == 'W' {
                cnt--
            }
            l++
        }
        r++
    }
    return ans
}

代码复盘

这次写代码又忘记 math.MaxInt 的拼写了，下次记住 mM 两个 m 打头

1052. 爱生气的书店老板

题目描述：难度分1418

代码与解题思路

老板克制生气的时间，就是题目要求的滑动窗口的大小；老板不生气的时间就是基础的顾客人数数值；老板生气的时间，就是我们需要使用滑动窗口取人数最多的地方了。在老板克制生气的时间内找顾客最多的那个区间

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
    l, r, n, sum, ans := 0, 0, len(customers), 0, -math.MaxInt/2
    for i, v := range customers {
        if grumpy[i] == 0 {
            sum += v
            customers[i] = 0 // 巧妙置零
        }
    }
    for r < n {
        sum += customers[r]
        if r-l == minutes-1 {
            ans = max(ans, sum)
            sum -= customers[l]
            l++
        }
        r++
    }
    return ans
}

代码复盘

在计算基础顾客数值的时候，将计算之后的顾客人数置为 0，后面使用滑动窗口的时候，就不需要进行 if grumpy[r] == 1 这样的判断了

2841. 几乎唯一子数组的最大和

题目描述：难度分1546

代码与解题思路

这道题的重点就在，如何判断题目要求的所谓 “几乎唯一子数组”。用哈希判断即可，可以用数组模拟，也可以用语言自带的库。

func maxSum(nums []int, m int, k int) int64 {
    l, r, n, sum, ans, win := 0, 0, len(nums), int64(0), int64(0), map[int]int{}
    for r < n {
        win[nums[r]]++
        sum += int64(nums[r])
        if r-l == k-1 {
            if len(win) >= m {
                ans = max(ans, sum)
            }
            win[nums[l]]--
            if win[nums[l]] == 0 {
                delete(win, nums[l])
            }
            sum -= int64(nums[l])
            l++
        }
        r++
    }
    return ans
}

代码复盘

这道题是经典的哈希+滑窗，我也是第一次用 go 写这个类型，刚好可以积累积累 go 使用 map 的技巧：

1、go 的 map 可以用 len() 计算有多少个键值对

2、使用 delete(map, key) 可以删除 map 中键为 key 的键值对

2461. 长度为 K 子数组中的最大和

题目描述：难度分1553

代码与解题思路

func maximumSubarraySum(nums []int, k int) int64 {
    l, r, n, sum, ans, win := 0, 0, len(nums), int64(0), int64(0), map[int]int{}
    for r < n {
        win[nums[r]]++
        sum += int64(nums[r])
        if r-l == k-1 {
            if len(win) == k {
                ans = max(ans, sum)
            }
            win[nums[l]]--
            if win[nums[l]] == 0 {
                delete(win, nums[l])
            }
            sum -= int64(nums[l])
            l++
        }
        r++
    }
    return ans
}

代码复盘

我的评价是跟上一道题目一毛一样，而且题目描述比上一道说的更加 “人话”。把 m 改成了 k 就过了。

1423. 可获得的最大点数

题目描述：难度分1574

代码与解题思路

题目说可以从行的开头或者结尾拿一张卡牌，求点数的最大和。由于我们只能从开头或末尾拿牌，所以最后剩下的牌必然是连续的，通过逆向思维，我们可以用滑动窗口求剩下的连续的卡牌的最小和，就能得出点数的最大和了。

func maxScore(cardPoints []int, k int) int {
    l, r, n, sumMin, sum, ans := 0, 0, len(cardPoints), 0, 0, math.MaxInt/2
    for r < n {
        sum += cardPoints[r]
        sumMin += cardPoints[r]
        if r-l == n-k-1 {
            ans = min(ans, sumMin)
            sumMin -= cardPoints[l]
            l++
        }
        r++
    }
    if k == len(cardPoints) { // 拿起所有卡牌
        return sum
    }
    return sum-ans
}

代码复盘

通过总数 sum - ans 最小和，我们就能求出题目要求的最大和。

2134. 最少交换次数来组合所有的 1 II

题目描述：难度分1748

代码与解题思路

这道题目也需要理解题目的要求，对题目的信息进行转化。题目要将所有 1 都聚集在一起，最差的情况我们需要把每个 1 都移动一遍，那我们可以让 1 的数量作为滑动窗口的大小，窗口中 1 存在的越多，证明需要移动的 1 就越少（窗口中全是 1 就是最后的答案）

func minSwaps(nums []int) int {
    k := 0
    for _, v := range nums {
        k += v
    }
    nums = append(nums, nums...) // 环形数组
    l, r, ans, sum, n := 0, 0, 0, 0, len(nums)
    for r < n { // 滑动窗口
        if nums[r] == 1 {
            sum++
        }
        if r-l == k-1 {
            ans = max(ans, sum)
            if nums[l] == 1 {
                sum--
            }
            l++
        }
        r++
    }
    return k-ans
}

代码复盘

1、使用 nums = append(nums, nums…) 将数组本身追加一份到数组后面，可以处理环形数组的问题

2653. 滑动子数组的美丽值

题目描述：难度分1786

代码与解题思路

这道题目的核心就在于，怎么判断一个数是不是美丽值，题目要求找倒数第 x 个数，如果每个都排序肯定会超时，也许可以用堆来维护区间内的单调性，但堆我用的不多，而且 go 的堆比较麻烦，我也没有什么好的思路

这道题目有一个可以利用的地方，他数据范围给了 -50~50，非常小，通过这个性质对整个数据范围进行计数，每次判断的时候：让 x 逐个减去当前值的个数，当 x < 0 或者 x = 0 的时候，证明当前这个数就是题目要找的美丽值了

func getSubarrayBeauty(nums []int, k int, x int) []int {
    cnt := [110]int{}   
    l, r, n := 0, 0, len(nums)
    ans := make([]int, n-k+1)
    for r < n {
        cnt[nums[r]+50]++
        if r-l == k-1 {
            t := x
            for i, v := range cnt[:50] {
                t -= v
                if t <= 0 { // 当前这个数是美丽值
                    ans[l] = i-50
                    break
                }
            }
            cnt[nums[l]+50]--
            l++
        }
        r++
    }
    return ans
}

代码复盘

1、注意观察题目的数据范围，说不定有可以利用的地方，就像本题利用计数排序的思想巧妙求出倒数第 x 个数

567. 字符串的排列

题目描述：难度分（无）

代码与解题思路

如何判断是两个子串是相同的排列是这道题的核心问题，我们可以通过 cnt 数组记录每个字母的个数，遍历的时候–，如果此时的 cnt 数组内都是正数，就证明这两个子串字符的数量相同，即符合题目的条件

func checkInclusion(s1 string, s2 string) bool {
    cnt, l, r, n := make([]int, 26), 0, 0, len(s2)
    for _, v := range s1 {
        cnt[v-'a']++
    }
    for r < n {
        cnt[s2[r]-'a']--
        if r-l == len(s1)-1 {
            flag := 0
            for _, v := range cnt {
                if v < 0 {
                    flag = 1
                }
            }
            if flag == 0 {
                return true
            }
            cnt[s2[l]-'a']++
            l++
        }
        r++
    }
    return false
}

代码复盘

1、Golang 也能通过 ‘a’ - ‘a’ 的形式获取到数字 0，通过这个性质我们可以构建字符数组 cnt

438. 找到字符串中所有字母异位词

题目描述：难度分（无）

代码与解题思路

这道题跟上一道题几乎一模一样，稍微修改，把下标存入数组返回即可

func findAnagrams(s string, p string) (ans []int) {
    cnt, l, r, n := make([]int, 26), 0, 0, len(s)
    for _, v := range p {
        cnt[v-'a']++
    }
    for r < n {
        cnt[s[r]-'a']--
        if r-l == len(p)-1 {
            flag := 0
            for _, v := range cnt {
                if v < 0 {
                    flag = 1
                }
            }
            if flag == 0 {
                ans = append(ans, l)
            }
            cnt[s[l]-'a']++
            l++
        }
        r++
    }
    return ans
}