标签： 滑动窗口

目标

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。

一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。

子数组 是原数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。

示例 2：

输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i], k <= 10^9

思路

返回数组 nums 的好子数组个数，好子数组定义为 子数组内至少有 k 对 (i, j) 满足 i < j 且 arr[i] == arr[j]。

可以使用滑动窗口，保证窗口内的子数组中至少包含 k 个合法数对。使用哈希表记录重复元素的个数，同时累加该重复元素新增加的数对个数，如果数对个数大于等于 k，收缩左边界直到数对个数小于 k，在循环中累加结果，子数组 [l, r ~ n - 1] 的个数为 n - r。当然也可以累加 子数组 [0 ~ l - 1, r] 个数为 l，结果是一样的。

代码

/**
 * @date 2025-04-16 8:39
 */
public class CountGood2537 {

    public long countGood(int[] nums, int k) {
        int n = nums.length;
        long res = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        int l = 0;
        int pairCnt = 0;
        for (int r = 0; r < n; r++) {
            pairCnt += cnt.getOrDefault(nums[r], 0);
            cnt.merge(nums[r], 1, Integer::sum);
            while (pairCnt >= k){
                res += n - r;
                cnt.merge(nums[l], -1, Integer::sum);
                pairCnt -= cnt.get(nums[l++]);
            }
        }
        return res;
    }

}

性能

目标

给你一个字符串 word 和一个 非负 整数 k。

返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。

示例 1：

输入：word = "aeioqq", k = 1
输出：0
解释：
不存在包含所有元音字母的子字符串。

示例 2：

输入：word = "aeiou", k = 0
输出：1
解释：
唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。

示例 3：

输入：word = "ieaouqqieaouqq", k = 1
输出：3
解释：
包含所有元音字母并且恰好含有一个辅音字母的子字符串有：
word[0..5]，即 "ieaouq"。
word[6..11]，即 "qieaou"。
word[7..12]，即 "ieaouq"。

说明：

• 5 <= word.length <= 2 * 10^5
• word 仅由小写英文字母组成。
• 0 <= k <= word.length - 5

思路

求给定字符串 word 的子字符串中至少包含 5 个元音且恰好包含 k 个辅音的子字符串个数。

与 3305.元音辅音字符串计数I 相比，字符串长度范围变成了 2 * 10^5。

恰好型滑动窗口，区间 [left, right] 满足条件不代表 [left, right + 1] 满足条件，可能辅音数量超过了 k，这样就不能累加前面的起点数量，需要重新遍历起点排除一个辅音，退化成暴力解法。

题解提到 恰好 k 个辅音字母 = 至少 k 个辅音字母 - 至少 k + 1 个辅音字母，这样就可以使用两个滑动窗口来求解。

代码

/**
 * @date 2025-03-13 17:03
 */
public class CountOfSubstrings3306 {

    public long countOfSubstrings(String word, int k) {
        return slidingWindow(word, k) - slidingWindow(word, k + 1);
    }

    public long slidingWindow(String word, int k) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
        Map<Character, Integer> map = new HashMap<>();
        int n = word.length();
        int consonantCnt = 0;
        long res = 0;
        int left = 0;
        for (int right = 0; right < n; right++) {
            char c = word.charAt(right);
            if (vowels.contains(c)) {
                Integer cnt = map.getOrDefault(c, 0);
                map.put(c, cnt + 1);
            } else {
                consonantCnt++;
            }
            while (left <= right && consonantCnt >= k && map.size() == 5) {
                c = word.charAt(left++);
                if (vowels.contains(c)) {
                    map.merge(c, -1, Integer::sum);
                    if (map.get(c) == 0) {
                        map.remove(c);
                    }
                } else {
                    consonantCnt--;
                }

            }
            res += left;
        }
        return res;
    }
}

性能

目标

给你一个字符串 word 和一个 非负 整数 k。

返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。

示例 1：

输入：word = "aeioqq", k = 1
输出：0
解释：
不存在包含所有元音字母的子字符串。

示例 2：

输入：word = "aeiou", k = 0
输出：1
解释：
唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。

示例 3：

输入：word = "ieaouqqieaouqq", k = 1
输出：3
解释：
包含所有元音字母并且恰好含有一个辅音字母的子字符串有：
word[0..5]，即 "ieaouq"。
word[6..11]，即 "qieaou"。
word[7..12]，即 "ieaouq"。

说明：

• 5 <= word.length <= 250
• word 仅由小写英文字母组成。
• 0 <= k <= word.length - 5

思路

求给定字符串 word 的子字符串中至少包含 5 个元音且恰好包含 k 个辅音的子字符串个数。

暴力枚举子数组。

代码

/**
 * @date 2025-03-12 8:42
 */
public class CountOfSubstrings3305 {

    public int countOfSubstrings(String word, int k) {
        int n = word.length();
        Set<Character> vowel = new HashSet<>();
        Collections.addAll(vowel, 'a', 'e', 'i', 'o', 'u');
        Map<Character, Integer> map = new HashMap<>();
        int consonantCnt = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = word.charAt(j);
                if (vowel.contains(c)) {
                    Integer cnt = map.getOrDefault(c, 0);
                    map.put(c, cnt + 1);
                } else {
                    consonantCnt++;
                }
                if (consonantCnt == k && map.size() == 5) {
                    res++;
                } else if (consonantCnt > k) {
                    break;
                }
            }
            map.clear();
            consonantCnt = 0;
        }
        return res;
    }

}

性能

目标

给你一个 下标从 1 开始的 整数数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。

水果超市有如下促销活动：

• 如果你花费 prices[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i + 1] 的水果。

注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以获得它的奖励。

请你返回获得所有水果所需要的 最少 金币数。

示例 1：

输入：prices = [3,1,2]
输出：4
解释：
用 prices[0] = 3 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
用 prices[1] = 1 个金币购买第 2 个水果，你可以免费获得第 3 个水果。
免费获得第 3 个水果。
请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

示例 2：

输入：prices = [1,10,1,1]
输出：2
解释：
用 prices[0] = 1 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 1 个金币购买第 3 个水果，你可以免费获得第 4 个水果。
免费获得第 4 个水果。

示例 3：

输入：prices = [26,18,6,12,49,7,45,45]
输出：39
解释：
用 prices[0] = 26 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 6 个金币购买第 3 个水果，你可以免费获得第 4，5，6（接下来的三个）水果。
免费获得第 4 个水果。
免费获得第 5 个水果。
用 prices[5] = 7 个金币购买第 6 个水果，你可以免费获得第 7 和 第 8 个水果。
免费获得第 7 个水果。
免费获得第 8 个水果。
请注意，即使您可以免费获得第 6 个水果作为购买第 3 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

说明：

1 <= prices.length <= 1000
1 <= prices[i] <= 10^5

思路

有 n 个水果，其价格由 prices 表示，当我们以 prices[i] 枚金币购买了第 i + 1 个苹果时，我们可以免费获得下标 [i + 1, i + i + 1] 的 所有 个苹果（当然也可以购买以获得后面的奖励），求获得全部苹果所需的最少硬币。

最直接的想法是记忆化搜索。

代码

/**
 * @date 2025-01-24 9:07
 */
public class MinimumCoins2944 {

    public int minimumCoins(int[] prices) {
        int[] mem = new int[2 * prices.length + 3];
        Arrays.fill(mem, Integer.MAX_VALUE);
        return dfs(0, prices, mem, 0);
    }

    public int dfs(int index, int[] prices, int[] mem, int cost) {
        int n = prices.length;
        if (index >= n) {
            return cost;
        }
        int res = cost + prices[index];
        int next = index * 2 + 2;
        if (mem[next] == Integer.MAX_VALUE) {
            mem[next] = dfs(next, prices, mem, 0);
        }
        int remainder = mem[next];
        if (remainder == 0) {
            return res;
        }
        for (int i = index + 1; i < n && i <= index * 2 + 1; i++) {
            if (mem[i] == Integer.MAX_VALUE) {
                mem[i] = dfs(i, prices, mem, 0);
            }
            remainder = Math.min(mem[i], remainder);
        }
        return res + remainder;
    }

}

性能

目标

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组 的长度，如果特别子数组不存在，那么返回 -1 。

示例 1：

输入：nums = [1,2,3], k = 2
输出：1
解释：
子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

示例 2：

输入：nums = [2,1,8], k = 10
输出：3
解释：
子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。

示例 3：

输入：nums = [1,2], k = 0
输出：1
解释：
子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。

说明：

• 1 <= nums.length <= 2 * 10^5
• 0 <= nums[i] <= 10^9
• 0 <= k <= 10^9

思路

求数组 nums 的最短特别子数组长度，特别子数组的所有元素按位与的结果大于等于 k。

与 3095.或值至少K的最短子数组I 相比数据范围变大了，O(n^2) 的解法会超时。

记录每一位的出现次数，使用滑动窗口，枚举右收缩左。由于 按位或 没有逆运算，我们可以反向重新计算 按位与。

代码

/**
 * @date 2025-01-17 8:40
 */
public class MinimumSubarrayLength3097 {

    public int minimumSubarrayLength_v2(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        int right = 0;
        int n = nums.length;
        int or = 0;
        while (right < n) {
            do {
                or |= nums[right++];
            } while (right < n && or < k);
            if (or >= k) {
                int left = right - 1;
                int tmp = 0;
                while (left >= 0) {
                    tmp |= nums[left--];
                    if (tmp >= k) {
                        left++;
                        break;
                    } else {
                        or = tmp;
                    }
                }
                res = Math.min(res, right - left);
            } else {
                break;
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

}

性能

目标

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀，那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法 子字符串 的数目。

示例 1：

输入：word1 = "bcca", word2 = "abc"
输出：1
解释：
唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。

示例 2：

输入：word1 = "abcabc", word2 = "abc"
输出：10
解释：
除了长度为 1 和 2 的所有子字符串都是合法的。

示例 3：

输入：word1 = "abcabc", word2 = "aaabc"
输出：0

说明：

• 1 <= word1.length <= 10^5
• 1 <= word2.length <= 10^4
• word1 和 word2 都只包含小写英文字母。

思路

有两个字符串 word1 和 word2，求 word1 有多个子字符串 满足子串的每个字符的出现次数 均大于等于 word2 中对应字符的出现次数。

暴力解法是枚举 word1 的每个子字符串，比较子串中的每个字符个数。具体来说就是统计 word1 与 word2 中各字符的个数，枚举 word1 起点，从后向前枚举终点，如果某字符个数小于 word2 相应字符的个数则停止计数，继续下一个起点。这种解法的时间复杂度是 O(n^2) 会超时。

考虑使用滑动窗口，当左边元素移出窗口时，向右扩展，直到移出的元素个数达到 word2 中对应字符的个数，累加右边界到结尾的字符个数。

代码

/**
 * @date 2025-01-09 14:28
 */
public class ValidSubstringCount3297 {

    public long validSubstringCount_v1(String word1, String word2) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        for (char c : chars1) {
            cnt1[c - 'a']++;
        }
        for (char c : chars2) {
            cnt2[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] < cnt2[i]) {
                return 0;
            }
        }
        int n = word1.length();
        int r = n - 1;
        while (--cnt1[chars1[r] - 'a'] >= cnt2[chars1[r] - 'a']) {
            r--;
        }
        long res = n - r;
        cnt1[chars1[r++] - 'a']++;
        for (int i = 0; i < n - word2.length(); i++) {
            int c = chars1[i] - 'a';
            cnt1[c]--;
            while (r < n && cnt1[c] < cnt2[c]) {
                cnt1[chars1[r++] - 'a']++;
            }
            if (cnt1[c] >= cnt2[c]) {
                res += n - r + 1;
            } else {
                break;
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 colors 和一个整数 k ，colors表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

• colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
• colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。

环中连续 k 块瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。

请你返回 交替 组的数目。

注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。

示例 1：

输入：colors = [0,1,0,1,0], k = 3
输出：3

解释：

交替组包括：

示例 2：

输入：colors = [0,1,0,0,1,0,1], k = 6
输出：2

解释：

交替组包括：

示例 3：

输入：colors = [1,1,0,1], k = 4
输出：0

解释：

说明：

• 3 <= colors.length <= 10^5
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

思路

有一个环形二进制数组（认为首尾相邻），如果连续的 k 个元素除了第一个与最后一个元素外，内部元素与它左边和右边的元素不同，则称这 k 个元素为一个交替组，求交替组的个数。

如果 k 取 3 就变成了 3206.交替组I。

昨天的题枚举的是中间元素，今天这道题我们可以枚举左端点。将其视为一个特殊的滑动窗口问题，特殊之处在于窗口内元素需要满足的条件是 不存在连续相等的元素。显然，如果新移入窗口的元素使得条件不满足，即窗口内后两个元素相等，那么只要窗口内包含这个新移入的元素 条件就总是无法满足。

因此可以直接将左端点移到右边界，省去了移出元素的滑动过程。在向右扩展的时候可以对窗口内的元素计数，如果大于等于 k 则计入结果，直到右端点无法再继续扩展，重置计数器，然后以右边界为左端点继续该过程。

可以省略维护左边界的指针，重置计数器就相当于从当前位置重新计数。

我们可以通过偏移下标然后取余来处理环形数组的遍历。也可以参考 134.加油站 两次循环。

代码

/**
 * @date 2024-11-26 9:31
 */
public class NumberOfAlternatingGroups3208 {

    /**
     * 两次循环1ms
     */
    public int numberOfAlternatingGroups_v2(int[] colors, int k) {
        int res = 0;
        int n = colors.length;
        int prev = colors[n - k + 1];
        int size = 1;
        for (int i = n - k + 2; i < n; i++) {
            if (colors[i] == prev) {
                size = 1;
            } else {
                size++;
            }
            prev = colors[i];
        }
        for (int i = 0; i < n; i++) {
            if (colors[i] == prev) {
                size = 1;
            } else {
                size++;
            }
            prev = colors[i];
            if (size >= k) {
                res++;
            }
        }
        return res;
    }

    /**
     * 5ms
     */
    public int numberOfAlternatingGroups_v1(int[] colors, int k) {
        int res = 0;
        int n = colors.length;
        int size = 1;
        for (int i = n - k + 2; i < 2 * n; i++) {
            if (colors[i % n] == colors[(i - 1) % n]) {
                size = 1;
            } else {
                size++;
            }
            if (size >= k) {
                res++;
            }
        }
        return res;
    }

}

性能