标签： 滑动窗口

3097.或值至少为K的最短子数组II

目标

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

}

性能

3298.统计重新排列后包含另一个字符串的子字符串数目II

目标

给你两个字符串 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^6
  • 1 <= word2.length <= 10^4
  • word1 和 word2 都只包含小写英文字母。

思路

参考 3297.统计重新排列后包含另一个字符串的子字符串数目I，本题内存限制小，必须使用线性复杂度的解法。

代码


/**
 * @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;
    }

}

性能

3297.统计重新排列后包含另一个字符串的子字符串数目I

目标

给你两个字符串 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;
    }

}

性能

3208.交替组II

目标

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

}

性能

632.最小区间

目标

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

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

说明：

  • nums.length == k
  • 1 <= k <= 3500
  • 1 <= nums[i].length <= 50
  • -10^5 <= nums[i][j] <= 10^5
  • nums[i] 按非递减顺序排列

思路

有 k 个非递减排列的整数列表，找一个最小区间，使得 k 个列表中每个列表至少有一个元素包含其中。所谓最小区间指区间长度最小，如果长度相同，则起点小的区间更小。

可以将元素标记属于哪个列表，然后从小到大排序，使用滑动窗口，找到最小的窗口。

当元素移入/移出窗口，如何判断是否应该从集合中增加/删除列表种类？

  • 可以记录每个列表元素的最大下标，如果移出的元素等于该下标则说明窗口内不包含该列表中的元素。元素移入窗口时可以根据最大下标是否小于左边界来判断是否应该增加列表种类，考虑到开始时左边界为 0，应该将数组初始化为 -1。
  • 也可以记录每个列表在窗口元素的个数，如果从 0 变为 1 则增加种类，如果从 1 变为 0 则减少。

代码


/**
 * @date 2024-11-24 15:14
 */
public class SmallestRange632 {

    /**
     * 优化代码逻辑
     */
    public int[] smallestRange_v1(List<List<Integer>> nums) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (Integer num : nums.get(i)) {
                list.add(new int[]{num, i});
            }
        }
        int[] res = new int[]{0, 1000000};
        list.sort((a, b) -> a[0] - b[0]);
        int n = list.size(), k = nums.size();
        int l = 0;
        int[] typeMaxIndex = new int[k];
        Arrays.fill(typeMaxIndex, -1);
        int types = 0;
        for (int r = 0; r < n; r++) {
            int[] e = list.get(r);
            int right = e[0];
            int type = e[1];
            int lastTypeMaxIndex = typeMaxIndex[type];
            typeMaxIndex[type] = r;
            if (lastTypeMaxIndex < l){
                types++;
            }
            while (types == k) {
                int[] left = list.get(l);
                int lType = left[1];
                if (typeMaxIndex[lType] == l++) {
                    types--;
                    if (right - left[0] < res[1] - res[0]) {
                        res[0] = left[0];
                        res[1] = right;
                    }
                }
            }
        }
        return res;
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (Integer num : nums.get(i)) {
                list.add(new int[]{num, i});
            }
        }
        int[] res = new int[]{0, 1000000};
        list.sort((a, b) -> a[0] - b[0]);
        int n = list.size(), k = nums.size();
        int l = 0;
        int[] typeMaxIndex = new int[k];
        Set<Integer> set = new HashSet<>();
        for (int r = 0; r < n; r++) {
            int[] e = list.get(r);
            int right = e[0];
            int type = e[1];
            typeMaxIndex[type] = r;
            set.add(type);
            while (set.size() == k) {
                int[] left = list.get(l);
                int lType = left[1];
                if (typeMaxIndex[lType] == l++) {
                    set.remove(lType);
                }
            }
            if (l >= 1 && !set.contains(list.get(l - 1)[1]) && set.size() == k - 1) {
                int left = list.get(l - 1)[0];
                if (right - left < res[1] - res[0]) {
                    res[0] = left;
                    res[1] = right;
                }
            }
        }
        return res;
    }
}

性能

825.适龄的朋友

目标

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

  • ages[y] <= 0.5 * ages[x] + 7
  • ages[y] > ages[x]
  • ages[y] > 100 && ages[x] < 100

否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

示例 1：

输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。

示例 2：

输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。

示例 3：

输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

说明：

  • n == ages.length
  • 1 <= n <= 2 * 10^4
  • 1 <= ages[i] <= 120

思路

某社交网站上有 n 个用户，ages[i] 表示用户 i 的年龄，当满足条件 ages[x] >= ages[y] && ages[y] > ages[x] / 2 + 7 时，用户 x 会向 y 发送好友申请。求网站上好友申请的总数。

第三个条件 ages[y] > 100 && ages[x] < 100 即 ages[y] > 100 > ages[x] 与第二个条件重复了，可以不考虑。

ages[x] >= ages[y] > ages[x] / 2 + 7 可以推出 ages[x] > 14 才可以发出好友申请，并且好友申请的对象也要满足 ages[y] > ages[x] / 2 + 7 > 14，

将年龄从大到小排序后，使用滑动窗口计算即可。

瓶颈在于排序，可以使用计数排序。

代码


/**
 * @date 2024-11-17 14:46
 */
public class NumFriendRequests825 {

    public int numFriendRequests_v1(int[] ages) {
        int n = ages.length;
        int[] ageCnt = new int[121];
        for (int i = 0; i < n; i++) {
            ageCnt[ages[i]]++;
        }
        int res = 0, windowCnt = 0;
        int l = 15;
        for (int i = 15; i < 121; i++) {
            windowCnt += ageCnt[i];
            if (l * 2 - 14 <= i) {
                windowCnt -= ageCnt[l++];
            }
            if (windowCnt > 0) {
                res += ageCnt[i] * (windowCnt - 1);
            }
        }
        return res;
    }

    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int n = ages.length;
        int r = n - 1, lowerBounds = ages[r] / 2 + 7;
        int res = 0;
        for (int l = n - 1; l >= 0 && ages[l] > 14; l--) {
            while (ages[l] <= lowerBounds) {
                lowerBounds = ages[--r] / 2 + 7;
            }
            res += r - l;
            int e = l;
            while (e < n - 1 && ages[e] == ages[e + 1]) {
                res++;
                e++;
            }
        }
        return res;
    }
}

性能

3261.统计满足K约束的子字符串数量II

目标

给你一个 二进制 字符串 s 和一个整数 k。

另给你一个二维整数数组 queries ，其中 queries[i] = [li, ri] 。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

  • 字符串中 0 的数量最多为 k。
  • 字符串中 1 的数量最多为 k。

返回一个整数数组 answer ，其中 answer[i] 表示 s[li..ri] 中满足 k 约束 的 子字符串 的数量。

示例 1：

输入：s = "0001111", k = 2, queries = [[0,6]]
输出：[26]
解释：
对于查询 [0, 6]， s[0..6] = "0001111" 的所有子字符串中，除 s[0..5] = "000111" 和 s[0..6] = "0001111" 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]
输出：[15,9,3]
解释：
s 的所有子字符串中，长度大于 3 的子字符串都不满足 k 约束。

说明：

  • 1 <= s.length <= 10^5
  • s[i] 是 '0' 或 '1'
  • 1 <= k <= s.length
  • 1 <= queries.length <= 10^5
  • queries[i] == [li, ri]
  • 0 <= li <= ri < s.length
  • 所有查询互不相同

思路

定义二进制字符串满足 k 约束的条件是字符串中 0 的个数 或者 1 的个数都不超过 k。求给定字符串满足 k 约束的子字符串数量。子字符串 是字符串中 连续 的 非空 字符序列。

这道题与昨天的 3258.统计满足K约束的子字符串数量I 相比多了一个查询数组，并且字符串的长度也来到了 10^5，返回结果是 long[]，暴力枚举会超时。

滑动窗口的时间复杂度为 O(n)，不可能对每一次查询都重新滑动一遍。显然需要在滑动的过程中记录下查询的结果。每次滑动我们可以得到一个区间 [l, r]，这个区间的所有子数组是合法的。

使用一维数组记录这个区间，使用下标与值的映射，我们有两种选择：

  • 记录的左端点的最大右端点，即 left[l] = r
  • 记录的右端点的最小左端点，即 right[r] = l

对于查询区间 [ql, qr]，它与我们已知的合法区间存在两种关系，被包含或者部分相交。

  • 如果是被包含的关系，那么查询区间的所有子数组均合法，子数组个数为 (qr - ql + 1) * (qr - ql + 2) / 2。
  • 如果是相交的关系，说明 ql < r，[ql, r] 的所有子数组是合法的，剩下的 [r + 1, qr] 的合法子数组如何求？可以在滑动过程中记录以每个元素为终点的合法子数组个数，以前缀和的形式保存。

这里区间的划分与结果集的构成是非常有讲究的。前缀和记录的是以元素为 终点 的合法子数组，如果我们在滑动的过程中根据查询区间终点匹配当前元素，即 qr == r，那么可能的情况为 ql >= l 查询区间被完全包含。如果 ql < l 则查询区间与合法区间相交。如果这时使用前缀和计算 [ql, l]，使用公式计算 [l, r] 就错了。因为后面区间使用公式计算的子数组并不包括以前面区间内的元素为起点的子数组，并且前缀和记录的子数组的起点可能在查询的左边界之外。而反过来前面使用公式计算，后面使用前缀和计算，被减去的那部分子数组个数中就包含了以 前面区间所有元素 为终点的子数组，也就是前面使用公式计算的子数组个数。我们不用担心后面通过前缀和计算的子数组的起点超出左边界，如果超出的话，一定是被包含的关系。

核心点在于想清楚这两部分集合的关系， [i, j] 的所有子数组包括了以 b ∈ [i, j] 为终点，a ∈ [i, b] 为起点的子数组。而使用前缀和相减计算的是所有以 c ∈ [m, n] 为终点的合法子数组，起点可以不在该区间，但是不会超出 ql。

代码


/**
 * @date 2024-11-13 0:25
 */
public class CountKConstraintSubstrings3261 {

    public long[] countKConstraintSubstrings_v1(String s, int k, int[][] queries) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] cnt = new int[2];
        long[] res = new long[queries.length];
        long[] prefix = new long[n + 1];
        int[] right = new int[n];
        Arrays.fill(right, n);
        int l = 0;
        for (int i = 0; i < n; i++) {
            cnt[chars[i] - '0']++;
            while (l <= i && cnt[0] > k && cnt[1] > k) {
                right[l] = i;
                cnt[chars[l++] - '0']--;
            }
            prefix[i + 1] += prefix[i] + i - l + 1;
        }
        for (int i = 0; i < queries.length; i++) {
            int ql = queries[i][0];
            int qr = queries[i][1];
            int r = Math.min(right[ql], qr + 1);
            res[i] = (r - ql + 1L) * (r - ql) / 2 + prefix[qr + 1] - prefix[r];

        }
        return res;
    }

}

性能

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

目标

给你一个 二进制 字符串 s 和一个整数 k。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

  • 字符串中 0 的数量最多为 k。
  • 字符串中 1 的数量最多为 k。

返回一个整数，表示 s 的所有满足 k 约束 的 子字符串 的数量。

示例 1：

输入：s = "10101", k = 1
输出：12
解释：
s 的所有子字符串中，除了 "1010"、"10101" 和 "0101" 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = "1010101", k = 2
输出：25
解释：
s 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。

示例 3：

输入：s = "11111", k = 1
输出：15
解释：
s 的所有子字符串都满足 k 约束。

说明：

  • 1 <= s.length <= 50
  • 1 <= k <= s.length
  • s[i] 是 '0' 或 '1'。

思路

定义二进制字符串满足 k 约束的条件是字符串中 0 的个数 或者 1 的个数都不超过 k。求给定字符串满足 k 约束的子字符串数量。子字符串 是字符串中 连续 的 非空 字符序列。

对于非定长滑动窗口，我们可以枚举左端点，扩展右端点；也可以枚举右端点，收缩左端点。对于这个题，我们需要累加的是子数组个数，即以枚举的元素为起点或终点的子数组个数，实际就是区间内元素个数。如果枚举左端点，右端点指向的是不满足条件的点，需要复杂的判断，非常容易出错。因此选择枚举右端点，收缩左端点。

代码


/**
 * @date 2024-11-12 9:19
 */
public class CountKConstraintSubstrings3258 {

    public int countKConstraintSubstrings(String s, int k) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] cnt = new int[2];
        int res = 0, l = 0;
        for (int i = 0; i < n; i++) {
            cnt[chars[i] - '0']++;
            while (l <= i && cnt[0] > k && cnt[1] > k) {
                cnt[chars[l++] - '0']--;
            }
            res += i - l + 1;
        }
        return res;
    }

}

性能

3254.长度为K的子数组的能量值I

目标

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

  • 如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
  • 否则为 -1 。

你需要求出 nums 中所有长度为 k 的 子数组 的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i..(i + k - 1)] 的能量值。

示例 1：

输入：nums = [1,2,3,4,3,2,5], k = 3
输出：[3,4,-1,-1,-1]
解释：
nums 中总共有 5 个长度为 3 的子数组：
[1, 2, 3] 中最大元素为 3 。
[2, 3, 4] 中最大元素为 4 。
[3, 4, 3] 中元素 不是 连续的。
[4, 3, 2] 中元素 不是 上升的。
[3, 2, 5] 中元素 不是 连续的。

示例 2：

输入：nums = [2,2,2,2,2], k = 4
输出：[-1,-1]

示例 3：

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

说明：

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

思路

有一个整数数组 nums，如果其子数组中的元素是连续且递增的，即公差为 1 的数列，定义子数组的能量值为子数组的最大元素，否则能量为 -1。返回所有长度为 k 的子数组的能量值。

显然需要使用滑动窗口，关键在于元素移入移出后如何判断是否连续且递增。我们可以使用队列记录不满足规则元素的 前一个 元素下标。当元素移入窗口时，判断元素与前一个元素是否满足规则，不满足则将前一个元素下标加入队列。窗口滑动时，先判断被移出的元素下标是否与队首相同，如果相同将队首元素删除。最后判断队列是否为空，如果为空则能量为新加入的元素，否则为 -1。

官网题解使用一个计数器记录连续递增的元素个数，初始化结果数组元素为 -1，当计数器大于等于 k 时，记录 i - k + 1 位置上的能量值为当前元素，否则将计数器重置为 1。

代码


/**
 * @date 2024-11-06 5:50
 */
public class ResultsArray3254 {

    public int[] resultsArray(int[] nums, int k) {
        int n = nums.length;
        if (k == 1) {
            return nums;
        }
        int[] res = new int[n - k + 1];
        Queue<Integer> q = new ArrayDeque<>();
        int l = 0, i = 0;
        for (int r = 1; r < n; r++) {
            int prev = r - 1;
            if (nums[r] - nums[prev] != 1) {
                q.offer(prev);
            }
            if (r - l + 1 > k) {
                if (!q.isEmpty() && l == q.peek()) {
                    q.poll();
                }
                l++;
            }
            if (r - l + 1 == k) {
                if (q.isEmpty()) {
                    res[i++] = nums[r];
                } else {
                    res[i++] = -1;
                }
            }
        }
        return res;
    }

}

性能

3171.找到按位或最接近K的子数组

目标

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。

请你返回 最小 的绝对差值。

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

示例 1：

输入：nums = [1,2,4,5], k = 3
输出：0
解释：
子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。

示例 2：

输入：nums = [1,3,1,3], k = 2
输出：1
解释：
子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。

示例 3：

输入：nums = [1], k = 10
输出：9
解释：
只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。

说明：

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

思路

寻找子数组使子数组元素按位或运算的值 or 尽可能地接近 k，即求 |k - or| 的最小值。

暴力求解的基本逻辑是，外层枚举右端点，内层从后向前枚举左端点，使用 nums[j] 保存 子数组 [j, i] 的或值，通过判断 (nums[j] | right) != nums[j] 决定 right 是否对或值有贡献，如果没有贡献，那么可以不再继续向前枚举左端点，因为前面的或值已经累加了后面的值，如果对子数组 [j, i] 的或值没有贡献，那么对前面的 [j - 1, i] 包含了 [j, i] 的或值更没有贡献。

代码


/**
 * @date 2024-10-09 8:59
 */
public class MinimumDifference3171 {

    public int minimumDifference_v1(int[] nums, int k) {
        int n = nums.length;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int right = nums[i];
            for (int j = i - 1; j >= 0 && ((nums[j] | right) != nums[j]); j--) {
                nums[j] |= right;
                res = Math.min(res, Math.abs(nums[j] - k));
            }
            res = Math.min(res, Math.abs(right - k));
        }
        return res;
    }

}

性能