标签： 滑动窗口

目标

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

说明：

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

思路

有一个正整数数组 nums，每一次操作可以移除剩余数组的最左或最右元素，求移除元素和等于 x 的最小操作数，如果不存在则返回 -1。

将问题转化为求子数组和为 sum - x 的最大长度，可以使用滑动窗口。

代码

/**
 * @date 2026-09-23 8:49
 */
public class MinOperations1658 {

    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < x) {
            return -1;
        } else if (sum == x) {
            return n;
        }
        int target = sum - x;
        int res = 0;
        int l = 0;
        sum = 0;
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            while (sum > target) {
                sum -= nums[l++];
            }
            if (sum == target) {
                res = Math.max(res, r - l + 1);
            }
        }
        return res == 0 ? -1 : n - res;
    }

}

性能

目标

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

示例 1：

输入：arr = [3,2,2,4,3], target = 3
输出：2
解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。

示例 2：

输入：arr = [7,3,4,7], target = 7
输出：2
解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。

示例 3：

输入：arr = [4,3,2,6,2,3,4], target = 6
输出：-1
解释：我们只有一个和为 6 的子数组。

示例 4：

输入：arr = [5,5,4,4,5], target = 3
输出：-1
解释：我们无法找到和为 3 的子数组。

示例 5：

输入：arr = [3,1,1,1,5,1,2,1], target = 3
输出：3
解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。

说明：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 1000
• 1 <= target <= 10^8

思路

有一个整数数组 arr 和一个整数值 target，从数组中找到两个不重叠的子数组，使得子数组的和为 target，返回这两个子数组长度之和的最小值。

将重叠问题进行前后缀分解，在各自的部分只需考虑和为 target 的最小长度，最小长度可以使用滑动窗口。

代码

/**
 * @date 2026-09-17 10:06
 */
public class MinSumOfLengths1477 {

    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        Arrays.fill(pre, Integer.MAX_VALUE);
        Arrays.fill(suf, Integer.MAX_VALUE);
        int sum = 0;
        int l = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            while (sum > target) {
                sum -= arr[l++];
            }
            if (sum == target) {
                pre[i + 1] = Math.min(pre[i], i - l + 1);
            } else {
                pre[i + 1] = pre[i];
            }
        }
        sum = 0;
        int r = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            sum += arr[i];
            while (sum > target) {
                sum -= arr[r--];
            }
            if (sum == target) {
                suf[i] = Math.min(suf[i + 1], r - i + 1);
            } else {
                suf[i] = suf[i + 1];
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (pre[i + 1] != Integer.MAX_VALUE && suf[i + 1] != Integer.MAX_VALUE) {
                res = Math.min(res, pre[i + 1] + suf[i + 1]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

}

性能

目标

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

一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。

如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。

请你返回 nums 中 最长好 子数组的长度。

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

示例 1：

输入：nums = [1,2,3,1,2,3,1,2], k = 2
输出：6
解释：最长好子数组是 [1,2,3,1,2,3] ，值 1 ，2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。
最长好子数组的长度为 6 。

示例 2：

输入：nums = [1,2,1,2,1,2,1,2], k = 1
输出：2
解释：最长好子数组是 [1,2] ，值 1 和 2 在子数组中的频率都没有超过 k = 1 。[2,1] 也是好子数组。
最长好子数组的长度为 2 。

示例 3：

输入：nums = [5,5,5,5,5,5,5], k = 4
输出：4
解释：最长好子数组是 [5,5,5,5] ，值 5 在子数组中的频率没有超过 k = 4 。
最长好子数组的长度为 4 。

说明：

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

思路

定义好子数组是元素频次不超过 k 的子数组，返回整数数组的最长好子数组长度。

滑动窗口。

代码

/**
 * @date 2026-08-12 9:19
 */
public class MaxSubarrayLength2958 {

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

}

性能

目标

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。

示例 1：

输出：low = 100, high = 300
输出：[123,234]

示例 2：

输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

说明：

• 10 <= low <= high <= 10^9

思路

定义顺序数字为从左到右每一位都比前一位的数字大 1 的整数。返回 [low, high] 范围内的所有顺序数字，按从小到大返回。

枚举数字长度以及开头数字，判断生成的顺序数字是否在 [low, high] 内即可。

代码

/**
 * @date 2026-07-13 9:10
 */
public class SequentialDigits1291 {

    public List<Integer> sequentialDigits(int low, int high) {
        int l = Integer.toString(low).length();
        int r = Integer.toString(high).length();
        List<Integer> res = new ArrayList<>();
        for (int i = l; i <= r; i++) {
            for(int j = 1; j + i <= 10; j++){
                Integer num = genInteger(j, i);
                if (low <= num && num <= high){
                    res.add(num);
                }
            }
        }
        return res;
    }

    public Integer genInteger(int first, int length) {
        int res = 0;
        for (int i = 0; i < length && first < 10; i++) {
            res = res * 10 + first;
            first++;
        }
        return res;
    }

}

性能

目标

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

示例 1：

输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。

示例 2：

输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。

示例 3：

输入：s = "abc"
输出：1

说明：

• 3 <= s.length <= 5 x 10^4
• s 只包含字符 a，b 和 c 。

思路

有一个字符串只包含三个字符 a b c，求这三个字符至少出现一次的子串个数。

直接的想法是计算这三个字符出现次数的前缀和，然后使用滑动窗口。使用前缀和来判断窗口内的子串是否满足条件，如果 [l, r] 满足条件，那么 [l, r ~ n - 1] 也满足条件。

判断字符是否至少出现一次可以不用前缀和，使用三个变量记录它们上次出现的下标，如果小于左端点则用 -1 标记。

代码

/**
 * @date 2026-06-30 9:14
 */
public class NumberOfSubstrings1358 {

    public int numberOfSubstrings(String s) {
        int n = s.length();
        int a = -1, b = -1, c = -1;
        int l = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'a') {
                a = i;
            } else if (s.charAt(i) == 'b') {
                b = i;
            } else {
                c = i;
            }
            while (a >= 0 && b >= 0 && c >= 0) {
                res += n - i;
                if (a <= l) {
                    a = -1;
                } else if (b <= l) {
                    b = -1;
                } else if (c <= l) {
                    c = -1;
                }
                l++;
            }
        }
        return res;
    }

}

性能

目标

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

• 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
• 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

• 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

说明：

• 1 <= s.length <= 10^5
• s[i] 要么是 '0' ，要么是 '1' 。

思路

有一个二进制字符串 s，每次操作：1.可以将首字母移动到末尾；2.或者将任意字符反转，求将 s 变为交替字符串所需的最小反转次数，即最少的操作 2 的次数。

由于不考虑首尾移动的次数，可以将首尾相接，考虑字符串 s + s。交替字符串就两种，可以使用长度为 s.length 的滑动窗口计算反转的最小次数。

可以只考虑交替字符串 010101... 所需的反转次数 k，那么 10101010... 所需的反转次数为 n - k，参考 1758_生成交替二进制字符串的最少操作数。

010101... 这种交替字符串可以用下标的奇偶性来表示。移出窗口时，如果下标的奇偶性与元素值的奇偶性不同，说明差异个数减一。移入窗口同理，操作次数加一。

代码

/**
 * @date 2026-03-09 11:42
 */
public class MinFlips1888 {

    public int minFlips(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int ops = 0;
        for (int i = 0; i < n; ++i) {
            ops += (chars[i] ^ i) & 1;
        }
        int res = Math.min(ops, n - ops);
        if ((n & 1) == 0) {
            return res;
        }
        for (int i = 0; i < n; ++i) {
            ops -= (chars[i] ^ i) & 1;
            ops += (chars[i] ^ (n + i)) & 1;
            res = Math.min(res, Math.min(ops, n - ops));
        }
        return res;
    }

}

性能

目标

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

• 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
• 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

• 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

说明：

• 1 <= s.length <= 10^5
• s[i] 要么是 '0' ，要么是 '1' 。

思路

有一个二进制字符串 s，每次操作：1.可以将首字母移动到末尾；2.或者将任意字符反转，求将 s 变为交替字符串所需的最小反转次数，即最少的操作 2 次数。

由于不考虑首尾移动的次数，可以将首尾相接，考虑字符串 s + s。交替字符串就两种，可以使用长度为 s.length 的滑动窗口计算反转的最小次数。

可以只考虑交替字符串 010101...，假设所需的反转次数为 k，那么 10101010... 所需的反转次数为 n - k，参考 1758.生成交替二进制字符串的最少操作数。

010101... 这种交替字符串可以用下标的奇偶性来表示。移出窗口时，如果下标的奇偶性与元素值的奇偶性不同，说明差异个数减一。移入窗口同理，操作次数加一。

代码

/**
 * @date 2026-03-09 11:42
 */
public class MinFlips1888 {

    public int minFlips(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int ops = 0;
        for (int i = 0; i < n; ++i) {
            ops += (chars[i] ^ i) & 1;
        }
        int res = Math.min(ops, n - ops);
        if ((n & 1) == 0) {
            // 如果长度为偶数，操作1不会改变下标的奇偶性，比如 i，i + n 的奇偶性相同，后面循环中 ops 并不会发生变化
            return res;
        }
        for (int i = 0; i < n; ++i) {
            ops -= (chars[i] ^ i) & 1;
            ops += (chars[i] ^ (n + i)) & 1;
            res = Math.min(res, Math.min(ops, n - ops));
        }
        return res;
    }

}

性能

目标

给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。

示例 1：

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

示例 2：

输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。

示例 3：

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

说明：

• 1 <= s.length <= 5 * 10^5
• s[i] 不是 '0' 就是 '1'
• 1 <= k <= 20

思路

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

长度为 k 的二进制子串的个数有 2^k 个，将子串视为二进制数字，使用长度为 k 的滑动窗口，记录窗口内子串表示的数字，判断是否所有数字都出现过即可。将左边界移出窗口需要将左边第一位置零 num = (num & (1 << (k - 1))) ^ num。先提取左边第一位，其余位均为 0，然后与 num 异或即可。

代码

/**
 * @date 2026-02-24 11:31
 */
public class HasAllCodes1461 {

    public boolean hasAllCodes(String s, int k) {
        if (k > 18) {
            return false;
        }
        int n = 1 << k;
        boolean[] visited = new boolean[n];
        int num = 0;
        char[] chars = s.toCharArray();
        int l = 0;
        for (int r = 0; r < chars.length; r++) {
            num = (num << 1) | (chars[r] - '0');
            if (r - l + 1 == k) {
                visited[num] = true;
                num = (num & (1 << (k - 1))) ^ num;
                l++;
            }
        }
        for (boolean b : visited) {
            if (!b) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

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

如果一个数组的 最大 元素的值 至多 是其 最小 元素的 k 倍，则该数组被称为是 平衡 的。

你可以从 nums 中移除 任意 数量的元素，但不能使其变为 空 数组。

返回为了使剩余数组平衡，需要移除的元素的 最小 数量。

注意：大小为 1 的数组被认为是平衡的，因为其最大值和最小值相等，且条件总是成立。

示例 1:

输入：nums = [2,1,5], k = 2
输出：1
解释：
移除 nums[2] = 5 得到 nums = [2, 1]。
现在 max = 2, min = 1，且 max <= min * k，因为 2 <= 1 * 2。因此，答案是 1。

示例 2:

输入：nums = [1,6,2,9], k = 3
输出：2
解释：
移除 nums[0] = 1 和 nums[3] = 9 得到 nums = [6, 2]。
现在 max = 6, min = 2，且 max <= min * k，因为 6 <= 2 * 3。因此，答案是 2。

示例 3:

输入：nums = [4,6], k = 2
输出：0
解释：
由于 nums 已经平衡，因为 6 <= 4 * 2，所以不需要移除任何元素。

说明：

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

思路

定义平衡数组是 元素最大值 <= k * 元素最小值 的数组。有一个数组 nums，每次操作可以移除一个元素，求使得数组变成平衡数组的最少操作次数。

直接二分查找大于 k * nums[i] 的最小下标 index，删掉的元素是前面 i 个元素（下标 i 其实是第 i + 1 个元素，前面有 i 个），加上 n - 1 - index + 1 个大于 k * nums[i] 的元素。

可以使用滑动窗口，删掉的元素就是总长度减去窗口内的元素，针对每一个 left 将其扩展到最右端，然后移出 left 继续判断。

代码

/**
 * @date 2026-02-06 8:54
 */
public class MinRemoval3634 {

    public int minRemoval(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int res = n - 1;
        int r = 0;
        for (int l = 0; l < n; l++) {
            while (r < n && (long) nums[l] * k >= nums[r]) {
                r++;
            }
            res = Math.min(res, n - (r - l));
        }
        return res;
    }

}

性能