标签： 滑动窗口

目标

给你一个整数数组 nums 和一个 正整数 k 。

请你统计有多少满足 「nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。

子数组是数组中的一个连续元素序列。

示例 1：

输入：nums = [1,3,2,3,3], k = 2
输出：6
解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。

示例 2：

输入：nums = [1,4,2,1], k = 3
输出：0
解释：没有子数组包含元素 4 至少 3 次。

说明：

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

思路

找出满足条件的子数组个数，子数组至少要包含 k 个最大元素。

代码

/**
 * @date 2025-04-29 8:50
 */
public class CountSubarrays2962 {

    public long countSubarrays(int[] nums, int k) {
        long res = 0L;
        int max = Arrays.stream(nums).max().orElse(1);
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            k -= nums[right] == max ? 1 : 0;
            while (k <= 0){
                k += nums[left++] == max ? 1 : 0;
            }
            res += left;
        }
        return res;
    }
}

性能

目标

给你一个由 正 整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

• 子数组中 不同 元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。

示例 1：

输入：nums = [1,3,1,2,2]
输出：4
解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。

示例 2：

输入：nums = [5,5,5,5]
输出：10
解释：数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。

说明：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2000

思路

求数组的完全子数组数目，完全子数组指包含数组中的所有不同元素的子数组。

使用哈希集合统计数组中的不同元素个数，使用滑动窗口统计符合条件的子数组数目。初始化时，记录窗口内元素的出现次数，直到包含所有不同元素。循环内如果缺少元素种类则扩展右边界，然后收缩左边界，直到移出元素的出现次数降为 0。

代码

/**
 * @date 2025-04-24 0:53
 */
public class CountCompleteSubarrays2799 {

    public int countCompleteSubarrays(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int max = 0;
        for (int num : nums) {
            set.add(num);
            max = Math.max(max, num);
        }
        int kinds = set.size();
        int left = 0, right = 0;
        set.clear();
        int[] cnt = new int[max + 1];
        while (set.size() < kinds) {
            cnt[nums[right]]++;
            set.add(nums[right++]);
        }
        int n = nums.length;
        int res = 0;
        int out = nums[left];
        do {
            while (right < n && cnt[out] == 0) {
                cnt[nums[right++]]++;
            }
            while (left < n && cnt[out] > 0) {
                res += n - right + 1;
                out = nums[left];
                cnt[nums[left++]]--;
            }
        } while (right < n);
        return res;
    }

}

性能

目标

给你一个整数数组 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;
    }

}

性能