算法笔试——滑动窗口

Updated Time 2024-10-24
Category
Tags

关于语言：一刷用 Golang，二刷用 Rust

题单来源于：分享丨【题单】滑动窗口与双指针（定长/不定长/至多/至少/恰好/单序列/双序列/三指针）

滑动窗口

套路

  1. 入：下标为 \(i\) 的元素进入窗口，更新相关统计量。如果 \(i < k - 1\) 则重复第一步。
  2. 更新：更新答案。一般是更新最大值/最小值。
  3. 出：下标为 \(i - k + 1\) 的元素离开窗口，更新相关统计量。

题单

定长滑动窗口：

题目 来源 难度 分数
1456. 定长子串中元音的最大数目 第 190 场周赛 Q2 中等 1263
643. 子数组最大平均数 I 简单
1343. 大小为 K 且平均值大于等于阈值的子数组数目 第 19 场双周赛 Q2 中等 1317
2090. 半径为 k 的子数组平均值 第 269 场周赛 Q2 中等 1358
2379. 得到 K 个黑块的最少涂色次数 第 85 场双周赛 Q1 简单 1360
1052. 爱生气的书店老板 第 138 场周赛 Q2 中等 1418
1461. 检查一个字符串是否包含所有长度为 K 的二进制子串 第 27 场双周赛 Q2 中等 1504
2841. 几乎唯一子数组的最大和 第 112 场双周赛 Q3 中等 1546
2461. 长度为 K 子数组中的最大和 第 318 场周赛 Q2 中等 1553
1423. 可获得的最大点数 第 186 场周赛 Q2 中等 1574
1297. 子串的最大出现次数 第 168 场周赛 Q3 中等 1748
2653. 滑动子数组的美丽值 第 342 场周赛 Q3 中等 1786

不定长滑动窗口：

题目 来源 难度 分数
3. 无重复字符的最长子串 中等
3090. 每个字符最多出现两次的最长子字符串 第 390 场周赛 Q1 简单 1329
1493. 删掉一个元素以后全为 1 的最长子数组 第 29 场双周赛 Q3 中等 1423
1208. 尽可能使字符串相等 第 156 场周赛 Q2 中等 1497
2730. 找到最长的半重复子字符串 第 106 场双周赛 Q2 中等 1502
904. 水果成篮 第 102 场周赛 Q2 中等 1516
1695. 删除子数组的最大得分 第 220 场周赛 Q2 中等 1529
2958. 最多 K 个重复元素的最长子数组 第 119 场双周赛 Q3 中等 1535
2779. 数组的最大美丽值 第 354 场周赛 Q2 中等 1638
2024. 考试的最大困扰度 第 62 场双周赛 Q3 中等 1643
1004. 最大连续1的个数 III 第 162 场周赛 Q3 中等 1656
1658. 将 x 减到 0 的最小操作数 第 215 场周赛 Q3 中等 1817
1838. 最高频元素的频数 第 238 场周赛 Q2 中等 1876
2516. 每种字符至少取 K 个 第 325 场周赛 Q2 中等 1948
2831. 找出最长等值子数组 第 359 场周赛 Q4 中等 1976

求最短/最小：

题目 来源 难度 分数
209. 长度最小的子数组 中等
2904. 最短且字典序最小的美丽子字符串 第 367 场周赛 Q2 中等 1483
1234. 替换子串得到平衡字符串 第 159 场周赛 Q3 中等 1878
2875. 无限数组的最短子数组 第 365 场周赛 Q3 中等 1914

求子数组个数，越长越合法： 滑动窗口的内层循环结束时，右端点固定在 \(right\)，左端点在 \(0, 1, 2, \cdots, left - 1\) 的所有子数组都是合法的，一共有 \(left\) 个，所以答案一般写 \(ans += left\)。

题目 来源 难度 分数
1358. 包含所有三种字符的子字符串数目 第 20 场双周赛 Q3 中等 1646
2962. 统计最大元素出现至少 K 次的子数组 第 375 场周赛 Q3 中等 1701
3325. 字符至少出现 K 次的子字符串 I 第 420 场周赛 Q2 中等
2799. 统计完全子数组的数目 第 356 场周赛 Q2 中等 1398
2537. 统计好子数组的数目 第 328 场周赛 Q3 中等 1892

求子数组个数，越短越合法： 滑动窗口的内层循环结束时，右端点固定在 \(right\)，左端点在 \(left, left + 1, \cdots, right\) 的所有子串都是合法的，这一共有 \(right - left + 1\) 个。

题目 来源 难度 分数
713. 乘积小于 K 的子数组 中等
3258. 统计满足 K 约束的子字符串数量 I 第 411 场周赛 Q1 简单 1258
2302. 统计得分小于 K 的子数组数目 第 80 场双周赛 Q4 困难 1808
2762. 不间断子数组 第 352 场周赛 Q3 中等 1940

恰好型滑动窗口：例如要计算多少个元素和恰好等于 \(k\)的子数组，可以把问题变成：

  • 计算有多少个元素和 \(\ge k\) 的子数组
  • 计算有多少个元素和 \(> k\)，也就是 \(\ge k+ 1\) 的子数组
题目 来源 难度 分数
930. 和相同的二元子数组 第 108 场周赛 Q2 中等 1592
1248. 统计「优美子数组」 第 161 场周赛 Q2 中等 1624

题解

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

func maxVowels(s string, k int) int {
    ans, cnt := 0, 0
    for i, v := range s {
        if v == 'a' || v == 'e' || v == 'i' || v == 'o' || v == 'u' {
            cnt++
        }
        if i < k - 1 {
            continue
        }
        ans = max(ans, cnt)
        out := s[i-k+1]
        if out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u' {
            cnt--
        }
    }
    return ans
}
impl Solution {
    pub fn max_vowels(s: String, k: i32) -> i32 {
        let s = s.as_bytes();
        let k = k as usize;
        let mut ans = 0;
        let mut vowel = 0;
        for (i, &c) in s.iter().enumerate() {
            if c == b'a' || c == b'e' || c == b'i' || c == b'o' || c == b'u' {
                vowel += 1;
            }
            if i < k - 1 {
                continue;
            }
            ans = ans.max(vowel);
            let out = s[i - k + 1];
            if out == b'a' || out == b'e' || out == b'i' || out == b'o' || out == b'u' {
                vowel -= 1;
            }
        }
        ans
    }
}

子数组最大平均数 I

func findMaxAverage(nums []int, k int) float64 {
    ans := math.MinInt
    sum := 0
    for i, num := range nums {
        sum += num
        if i < k - 1 {
            continue
        }
        ans = max(ans, sum)
        sum -= nums[i-k+1]
    }
    return float64(ans) / float64(k)
}
impl Solution {
    pub fn find_max_average(nums: Vec<i32>, k: i32) -> f64 {
        let mut sum: i32 = nums.iter().take(k as usize).sum();
        let mut ans = sum;
        for i in (k as usize)..nums.len() {
            sum = sum + nums[i] - nums[i - k as usize];
            ans = ans.max(sum);
        }
        ans as f64 / k as f64
    }
}

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

func numOfSubarrays(arr []int, k int, threshold int) int {
    ans, sum := 0, 0
    for i, v := range arr {
        sum += v
        if i < k - 1 {
            continue
        }
        if sum / k >= threshold {
            ans++
        }
        sum -= arr[i-k+1]
    }
    return ans
}
impl Solution {
    pub fn num_of_subarrays(arr: Vec<i32>, k: i32, threshold: i32) -> i32 {
        let mut sum: i32 = 0;
        let mut ans = 0;
        for (i, a) in arr.iter().enumerate() {
            sum += a;
            if i < k as usize - 1 {
                continue;
            }
            if sum / k >= threshold {
                ans += 1;
            }
            sum -= arr[i - k as usize + 1];
        }
        ans
    }
}

半径为 k 的子数组平均值

func getAverages(nums []int, k int) []int {
    sum := 0
    ans := make([]int, len(nums))
    for i := range ans {
        ans[i] = -1
    }
    for i, num := range nums {
        sum += num
        if i < 2 * k {
            continue
        }
        ans[i-k] = sum / (2 * k + 1)
        sum -= nums[i-2*k]
    }
    return ans
}
impl Solution {
    pub fn get_averages(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut sum: i64 = 0;
        let mut ans: Vec<i32> = vec![-1; nums.len()];
        for (i, &a) in nums.iter().enumerate() {
            sum += a as i64;
            if i < 2 * (k as usize) {
                continue;
            }
            ans[i - k as usize] = (sum / (2 * k + 1) as i64) as i32;
            sum -= nums[i - (2 * k as usize)] as i64;
        }
        ans
    }
}

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

func minimumRecolors(blocks string, k int) int {
    ans := len(blocks)
    cnt := 0
    for i, b := range blocks {
        if b == 'W' {
            cnt++
        }
        if i < k - 1 {
            continue
        }
        ans = min(ans, cnt)
        if blocks[i-k+1] == 'W' {
            cnt--
        }
    }
    return ans
}
impl Solution {
    pub fn minimum_recolors(blocks: String, k: i32) -> i32 {
        let s = blocks.as_bytes();
        let mut ans: i32 = blocks.len() as i32;
        let mut cnt: i32 = 0;
        for (i, &c) in s.iter().enumerate() {
            if c == b'W' {
                cnt += 1;
            }
            if (i as i32) < k - 1 {
                continue
            }
            ans = ans.min(cnt);
            if s[i - k as usize + 1] == b'W' {
                cnt -= 1;
            }
        }
        ans
    }
}

爱生气的书店老板

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
    ans, sum := 0, 0
    for i, v := range customers {
        if grumpy[i] == 0 {
            sum += v
        }
    }
    ans = sum
    for i, v := range customers {
        if grumpy[i] == 1 {
            sum += v
        }
        if i < minutes - 1 {
            continue
        }
        ans = max(ans, sum)
        if grumpy[i-minutes+1] == 1 {
            sum -= customers[i-minutes+1]
        }
    }
    return ans
}
impl Solution {
    pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, minutes: i32) -> i32 {
        let mut ans = 0;
        let mut sum: i32 = 0;
        for (i, &v) in customers.iter().enumerate() {
            if grumpy[i] == 0 {
                sum += v;
            }
        }
        ans = sum;
        for (i, &v) in customers.iter().enumerate() {
            if grumpy[i] == 1 {
                sum += v;
            }
            if (i as i32) < minutes - 1 {
                continue;
            }
            ans = ans.max(sum);
            if grumpy[i - minutes as usize + 1] == 1 {
                sum -= customers[i - minutes as usize + 1];
            }
        }
        ans
    }
}

检查一个字符串是否包含所有长度为 K 的二进制子串

func hasAllCodes(s string, k int) bool {
    vi := make(map[int]struct{})
    cur := 0
    for i, v := range s {
        cur = cur << 1 + int(v - '0')
        if i < k - 1 {
            continue
        }
        vi[cur] = struct{}{}
        cur &= (1 << (k - 1)) - 1
    }
    return len(vi) == (1 << k)
}

几乎唯一子数组的最大和

func maxSum(nums []int, m int, k int) int64 {
    ans, sum := int64(0), int64(0)
    cnt := make(map[int]int)
    for i, num := range nums {
        sum += int64(num)
        cnt[num]++
        if i < k - 1 {
            continue
        }
        if len(cnt) >= m {
            ans = max(ans, sum)
        }
        out := nums[i-k+1]
        sum -= int64(out)
        cnt[out]--
        if cnt[out] == 0 {
            delete(cnt, out)
        }
    }
    return ans
}

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

func maximumSubarraySum(nums []int, k int) int64 {
    cnt := make(map[int]int)
    ans, sum := int64(0), int64(0)
    for i, num := range nums {
        sum += int64(num)
        cnt[num]++
        if i < k - 1 {
            continue
        }
        if len(cnt) == k {
            ans = max(ans, sum)
        }
        out := nums[i-k+1]
        sum -= int64(out)
        cnt[out]--
        if cnt[out] == 0 {
            delete(cnt, out)
        }
    }
    return ans
}

可获得的最大点数

逆向思维：拿走 \(k\) 张，剩下 \(n-k\) 张。这里 \(n\) 是 \(cardPoints\) 的长度。

由于拿走的点数和 + 剩下的点数和 = 所以点数和 = 常数，所以为了最大化拿走的点数和，应当最小化剩下的点数和。

由于只能从开头或末尾拿牌，所以最后剩下的牌必然是连续的。

func maxScore(cardPoints []int, k int) int {
    sum := 0
    for i := 0; i < k; i++ {
        sum += cardPoints[i]
    }
    ans := sum
    for i, j := k - 1, len(cardPoints) - 1; i >= 0 && j >= 0; i, j = i - 1, j - 1 {
        sum = sum - cardPoints[i] + cardPoints[j]
        ans = max(ans, sum)
    }
    return ans
}
impl Solution {
    pub fn max_score(card_points: Vec<i32>, k: i32) -> i32 {
        let n = card_points.len();
        let m = n - k as usize;
        let mut s = card_points.iter().take(m).sum::<i32>();
        let mut min_s = s;
        for i in m..n {
            s += card_points[i] - card_points[i-m];
            min_s = min_s.min(s);
        }
        card_points.iter().sum::<i32>() - min_s
    }
}

子串的最大出现次数

func maxFreq(s string, maxLetters int, minSize int, maxSize int) int {
    cnt := make(map[string]int)
    vi := make(map[byte]int)
    bs := []byte(s)
    ans := 0
    sub := ""
    for i, v := range bs {
        sub += string(v)
        vi[v]++
        if i < minSize - 1 {
            continue
        }
        if len(vi) <= maxLetters {
            cnt[sub]++
            ans = max(ans, cnt[sub])
        }
        vi[s[i-minSize+1]]--
        if vi[s[i-minSize+1]] == 0 {
            delete(vi, s[i-minSize+1])
        }
        sub = sub[1:]
    }
    return ans
}

滑动子数组的美丽值

func getSubarrayBeauty(nums []int, k int, x int) []int {
    offset := 50
    cnt := make([]int, 110)
    ans := []int{}
    for i, num := range nums {
        cnt[num+offset]++
        if i < k - 1 {
            continue
        }
        idx := x
        for i := 0; i < 110; i++ {
            idx -= cnt[i]
            if idx <= 0 {
                ans = append(ans, min(i-offset, 0))
                break
            }
        }
        cnt[nums[i-k+1]+offset]--
    }
    return ans
}

无重复字符的最长子串

func lengthOfLongestSubstring(s string) (ans int) {
    window := [128]bool{} // 也可以用 map，这里为了效率用的数组
    left := 0
    for right, c := range s {
        // 如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素
        // 所以要在加入 c 之前，先移出窗口内的 c
        for window[c] { // 窗口内有 c
            window[s[left]] = false
            left++ // 缩小窗口
        }
        window[c] = true // 加入 c
        ans = max(ans, right-left+1) // 更新窗口长度最大值
    }
    return
}

每个字符最多出现两次的最长子字符串

func maximumLengthSubstring(s string) int {
    cnt := [26]int{}
    ans, left := 0, 0
    for right, b := range s {
        cnt[b-'a']++
        for cnt[b-'a'] > 2 {
            cnt[s[left]-'a']--
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans
}

删掉一个元素以后全为 1 的最长子数组

转换为不定长滑动窗口，只允许删除一个元素，也就是说在窗口内最多包含一个 \(0\)。 

func longestSubarray(nums []int) int {
    ans, zero := 0, 0
    left := 0
    for right, num := range nums {
        zero += (1 - num)
        for zero > 1 {
            zero -= (1 - nums[left])
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans - 1
}

尽可能使字符串相等

func equalSubstring(s string, t string, maxCost int) int {
    bs, ts := []byte(s), []byte(t)
    ans, cost := 0, 0
    left := 0
    for right := range bs {
        cost += abs(int(bs[right]) - int(ts[right]))
        fmt.Println(cost)
        if cost > maxCost {
            cost -= abs(int(bs[left]) - int(ts[left]))
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans
}

func abs(v int) int {
    if v < 0 {
        return -v
    }
    return v
}

找到最长的半重复子字符串

func longestSemiRepetitiveSubstring(s string) int {
    if len(s) == 1 {
        return 1
    }
    ans := 0
    cnt, left := 0, 0
    for right, a := range s {
        if right == 0 {
            continue
        }
        if byte(a) == s[right - 1] {
            cnt++
        }
        for cnt > 1 {
            if s[left] == s[left+1] {
                cnt--
            }
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans
}

水果成篮

func totalFruit(fruits []int) int {
    ans := 0 
    cnt := make(map[int]int)
    left := 0
    for right, fruit := range fruits {
        cnt[fruit]++
        for len(cnt) > 2 {
            cnt[fruits[left]]--
            if cnt[fruits[left]] == 0 {
                delete(cnt, fruits[left])
            }
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans
}

删除子数组的最大得分

func maximumUniqueSubarray(nums []int) int {
    cnt := [10010]int{}
    ans, sum, left := 0, 0, 0
    for _, num := range nums {
        sum += num
        cnt[num]++
        for cnt[num] > 1 {
            cnt[nums[left]]--
            sum -= nums[left]
            left++
        }
        ans = max(ans, sum)
    }
    return ans
}

最多 K 个重复元素的最长子数组

func maxSubarrayLength(nums []int, k int) int {
    cnt := make(map[int]int)
    ans, left := 0, 0
    for right, num := range nums {
        cnt[num]++
        for cnt[num] > k {
            cnt[nums[left]]--
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans
}

数组的最大美丽值

由于选的是子序列，且操作后子序列的元素都相等，所以元素顺序对答案没有影响，可以先对数组排序。

func maximumBeauty(nums []int, k int) int {
    slices.Sort(nums)
    ans, left := 0, 0
    for right, x := range nums {
        for x - nums[left] > k * 2 {
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans
}

考试的最大困扰度

由于子串越长，越无法满足要求，有单调性，可以用滑动窗口解决。

如果 \(T\) 和 \(F\) 的出现次数都超过 \(k\)，那么必须不断移动左端点 \(left\)，同时减少 \(answerKey[left]\) 的出现次数，直到 \(T\) 和 \(F\) 的出现次数至少有一个 \(\le k\)。

代码实现时，由于 \(T\) 和 \(F\) 的 ASCII 值除以 \(2\) 后的奇偶性不同，也就是它们二进制的次低位不同，可以改为统计二进制次低位。

// 两次遍历
func maxConsecutiveAnswers(answerKey string, k int) int {
    ans := 0
    t_cnt, f_cnt := 0, 0
    left := 0
    for right, key := range answerKey {
        if key == 'F' {
            f_cnt++
        }
        for f_cnt > k {
            if answerKey[left] == 'F' {
                f_cnt--
            }
            left++
        }
        ans = max(ans, right - left + 1)
    }
    left = 0
    for right, key := range answerKey {
        if key == 'T' {
            t_cnt++
        }
        for t_cnt > k {
            if answerKey[left] == 'T' {
                t_cnt--
            }
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans
}
// 一次遍历
func maxConsecutiveAnswers(answerKey string, k int) int {
    ans := 0
    cnt := [2]int{}
    left := 0
    for right, ch := range answerKey {
        cnt[ch>>1&1]++
        for cnt[0] > k && cnt[1] > k {
            cnt[answerKey[left]>>1&1]--
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans
}

最大连续1的个数 III

func longestOnes(nums []int, k int) int {
    ans := 0
    left, zero_cnt := 0, 0
    for right, num := range nums {
        zero_cnt += 1 - num
        for zero_cnt > k {
            zero_cnt -= 1 - nums[left]
            left++
        }
        ans = max(ans, right - left + 1)
    }
    return ans
}

将 x 减到 0 的最小操作数

逆向思维，把问题转换成从 \(nums\) 中移除一个最长的子数组，使得剩余元素的和为 \(x\)。换句话说，要从 \(nums\) 中找最长的子数组，其元素和等于 \(s-x\)，这里的 \(s\) 为 \(nums\) 所有元素之和。

func minOperations(nums []int, x int) int {
    target := 0
    for _, v := range nums {
        target += v
    }
    target -= x
    if target < 0 {
        return -1
    }
    ans, sum, left := -1, 0, 0
    for right, num := range nums {
        sum += num
        for sum > target  {
            sum -= nums[left]
            left++
        }
        if sum == target {
            ans = max(ans, right - left + 1)
        }
    }
    if ans < 0 {
        return -1
    }
    return len(nums) - ans
}

最高频元素的频数

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)
    ans := 1
    for l, r, total := 0, 1, 0; r < len(nums); r++ {
        total += (nums[r] - nums[r-1]) * (r - l)
        for total > k {
            total -= nums[r] - nums[l]
            l++
        }
        ans = max(ans, r - l + 1)
    }
    return ans
}

每种字符至少取 K 个

每种字母至少取走 \(k\) 个，等价于剩下的字母至多有 \(n-k\) 个。由于只能从 \(s\) 最左侧和最右侧取走字母，所以剩下的字母是 \(s\) 的子串。

func takeCharacters(s string, k int) int {
    bs := []byte(s)
    total := [3]int{}
    for _, v := range bs {
        total[v-'a']++
    }
    if total[0] < k || total[1] < k || total[2] < k {
        return -1
    }
    ans, left := -1, 0
    cnt := [3]int{}
    for right, v := range bs {
        cnt[v-'a']++
        for total[v-'a'] - cnt[v-'a'] < k {
            cnt[bs[left]-'a']--
            left++
        }
        ans = max(ans, right - left + 1)
        
    }
    return len(s) - ans
}

找出最长等值子数组

相同元素分组，对每种数字做滑动窗口，需要注意需要删除的个数和保留的个数。

func longestEqualSubarray(nums []int, k int) int {
    list := make([][]int, len(nums) + 1)
    for i, num := range nums {
        list[num] = append(list[num], i)
    }
    ans := 0
    for _, l := range list {
        if len(l) < ans {
            continue
        }
        left := 0
        for right, pos := range l {
            for pos - l[left] - (right - left) > k {
                left++
            }
            ans = max(ans, right - left + 1)
        }
    }
    return ans
}

找出最长等值子数组

func minSubArrayLen(target int, nums []int) int {
    ans := len(nums) + 1
    left, s := 0, 0
    for right, num := range nums {
        s += num
        for s >= target {
            ans = min(ans, right - left + 1)
            s -= nums[left]
            left++
        }
    }
    if ans > len(nums) {
        return 0
    }
    return ans
}

最短且字典序最小的美丽子字符串

func shortestBeautifulSubstring(s string, k int) string {
    if strings.Count(s, "1") < k {
        return ""
    }
    ans := s
    left, cnt := 0, 0
    for right, b := range s {
        cnt += int(b & 1)
        for cnt > k || s[left] == '0' {
            cnt -= int(s[left] & 1)
            left++
        }
        if cnt == k {
            t := s[left : right + 1]
            if len(t) < len(ans) || len(t) == len(ans) && t < ans {
                ans = t
            }
        }
    }
    return ans
}

替换子串得到平衡字符串

func balancedString(s string) int {
    cnt, m := ['X']int{}, len(s) / 4
    for _, c := range s {
        cnt[c]++
    }
    if cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m {
        return 0
    }
    ans, left := len(s), 0
    for right, c := range s {
        cnt[c]--
        for cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m {
            ans = min(ans, right - left + 1)
            cnt[s[left]]++
            left++
        }
    }
    return ans
}

无限数组的最短子数组

func minSizeSubarray(nums []int, target int) int {
    total := 0
    for _, x := range nums {
        total += x
    }
    ans := math.MaxInt
    left, sum, n := 0, 0, len(nums)
    for right := 0; right < n * 2; right++ {
        sum += nums[right%n]
        for sum > target % total {
            sum -= nums[left%n]
            left++
        }
        if sum == target % total {
            ans = min(ans, right - left + 1)
        }
    }
    if ans == math.MaxInt {
        return -1
    }
    return ans + target / total * n
}

包含所有三种字符的子字符串数目

func numberOfSubstrings(s string) (ans int) {
    left, cnt := 0, [3]int{}
    bs := []byte(s)
    for _, b := range bs {
        cnt[b-'a']++
        for cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0 {
            cnt[bs[left]-'a']--
            left++
        }
        ans += left
    }
    return
}

统计最大元素出现至少 K 次的子数组

func countSubarrays(nums []int, k int) int64 {
    mx := 0
    for _, num := range nums {
        mx = max(mx, num)
    }
    ans, cnt, left := int64(0), 0, 0
    for _, num := range nums {
        if num == mx {
            cnt++
        }
        for cnt >= k {
            if nums[left] == mx {
                cnt--
            }
            left++
        }
        ans += int64(left)
    }
    return ans
}

字符至少出现 K 次的子字符串 I

func numberOfSubstrings(s string, k int) (ans int) {
    bs := []byte(s)
    left, cnt := 0, [26]int{} 
    for _, b := range bs {
        cnt[b-'a']++
        for cnt[b-'a'] >= k {
            cnt[bs[left]-'a']--
            left++
        }
        ans += left
    }
    return
}

统计完全子数组的数目

func countCompleteSubarrays(nums []int) (ans int) {
    cnt1 := make(map[int]int)
    for _, num := range nums {
        cnt1[num]++
    }
    left, cnt2 := 0, make(map[int]int)
    for _, num := range nums {
        cnt2[num]++
        for len(cnt2) == len(cnt1) {
            cnt2[nums[left]]--
            if cnt2[nums[left]] == 0 {
                delete(cnt2, nums[left])
            }
            left++
        }
        ans += left
    }
    return
}

统计好子数组的数目

func countGood(nums []int, k int) (ans int64) {
    left, cnt, n := 0, make(map[int]int), 0
    for _, num := range nums {
        n += cnt[num]
        cnt[num]++
        for n >= k {
            cnt[nums[left]]--
            n -= cnt[nums[left]]
            left++
        }
        ans += int64(left)
    }
    return
}

乘积小于 K 的子数组

func numSubarrayProductLessThanK(nums []int, k int) int {
    if k <= 1 {
        return 0
    }
    left, mul, ans := 0, 1, 0
    for right, num := range nums {
        mul *= num
        for mul >= k {
            mul /= nums[left]
            left++
        }
        ans += right - left + 1
    }
    return ans
}

统计满足 K 约束的子字符串数量 I

func countKConstraintSubstrings(s string, k int) int {
    bs := []byte(s)
    left, cnt, ans := 0, [2]int{}, 0
    for right, b := range bs {
        cnt[b-'0']++
        for cnt[0] > k && cnt[1] > k {
            cnt[bs[left]-'0']--
            left++
        }
        ans += right - left + 1
    }
    return ans
}

统计得分小于 K 的子数组数目

func countSubarrays(nums []int, k int64) (ans int64) {
    left, sum := 0, int64(0)
    for right, num := range nums {
        sum += int64(num)
        for sum * int64(right - left + 1) >= k {
            sum -= int64(nums[left])
            left++
        }
        ans += int64(right - left + 1)
    }
    return
}

不间断子数组

class Solution {
public:
    long long continuousSubarrays(vector<int> &nums) {
        long long ans = 0;
        multiset<int> s;
        int left = 0, n = nums.size();
        for (int right = 0; right < n; right++) {
            s.insert(nums[right]);
            while (*s.rbegin() - *s.begin() > 2) {
                s.erase(s.find(nums[left++]));
            }
            ans += right - left + 1;
        }
        return ans;
    }
};

和相同的二元子数组

func numSubarraysWithSum(nums []int, goal int) int {
    var f func(k int) int
    f = func(k int) int {
        ans, left, sum := 0, 0, 0
        for right, num := range nums {
            sum += num
            for sum >= k && left <= right {
                sum -= nums[left]
                left++
            }
            ans += left
        }
        return ans
    }
    return f(goal) - f(goal+1)
}

统计「优美子数组」

func numberOfSubarrays(nums []int, k int) int {
    var f func(k int) int
    f = func(k int) int {
        left, ans, cnt := 0, 0, 0
        for _, num := range nums {
            cnt += num & 1
            for cnt >= k {
                cnt -= nums[left] & 1
                left++
            }
            ans += left
        }
        return ans
    }
    return f(k) - f(k+1)
}
  1. 1. 滑动窗口
    1. 1.1. 套路
    2. 1.2. 题单
    3. 1.3. 题解
      1. 1.3.1. 定长子串中元音的最大数目
      2. 1.3.2. 子数组最大平均数 I
      3. 1.3.3. 大小为 K 且平均值大于等于阈值的子数组数目
      4. 1.3.4. 半径为 k 的子数组平均值
      5. 1.3.5. 得到 K 个黑块的最少涂色次数
      6. 1.3.6. 爱生气的书店老板
      7. 1.3.7. 检查一个字符串是否包含所有长度为 K 的二进制子串
      8. 1.3.8. 几乎唯一子数组的最大和
      9. 1.3.9. 长度为 K 子数组中的最大和
      10. 1.3.10. 可获得的最大点数
      11. 1.3.11. 子串的最大出现次数
      12. 1.3.12. 滑动子数组的美丽值
      13. 1.3.13. 无重复字符的最长子串
      14. 1.3.14. 每个字符最多出现两次的最长子字符串
      15. 1.3.15. 删掉一个元素以后全为 1 的最长子数组
      16. 1.3.16. 尽可能使字符串相等
      17. 1.3.17. 找到最长的半重复子字符串
      18. 1.3.18. 水果成篮
      19. 1.3.19. 删除子数组的最大得分
      20. 1.3.20. 最多 K 个重复元素的最长子数组
      21. 1.3.21. 数组的最大美丽值
      22. 1.3.22. 考试的最大困扰度
      23. 1.3.23. 最大连续1的个数 III
      24. 1.3.24. 将 x 减到 0 的最小操作数
      25. 1.3.25. 最高频元素的频数
      26. 1.3.26. 每种字符至少取 K 个
      27. 1.3.27. 找出最长等值子数组
      28. 1.3.28. 找出最长等值子数组
      29. 1.3.29. 最短且字典序最小的美丽子字符串
      30. 1.3.30. 替换子串得到平衡字符串
      31. 1.3.31. 无限数组的最短子数组
      32. 1.3.32. 包含所有三种字符的子字符串数目
      33. 1.3.33. 统计最大元素出现至少 K 次的子数组
      34. 1.3.34. 字符至少出现 K 次的子字符串 I
      35. 1.3.35. 统计完全子数组的数目
      36. 1.3.36. 统计好子数组的数目
      37. 1.3.37. 乘积小于 K 的子数组
      38. 1.3.38. 统计满足 K 约束的子字符串数量 I
      39. 1.3.39. 统计得分小于 K 的子数组数目
      40. 1.3.40. 不间断子数组
      41. 1.3.41. 和相同的二元子数组
      42. 1.3.42. 统计「优美子数组」
Copyright 2024 Cheryl-Chun