标签： 滑动窗口

目标

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或运算值 。

• 换言之，令 Bij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。

一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。

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

示例 1：

输入：nums = [1,0,2,1,3]
输出：[3,3,2,2,1]
解释：
任何位置开始，最大按位或运算的结果都是 3 。
- 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
- 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
- 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
- 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
- 下标 4 处，能得到结果 3 的最短子数组是 [3] 。
所以我们返回 [3,3,2,2,1] 。

示例 2：

输入：nums = [1,2]
输出：[2,1]
解释：
下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。
下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。
所以我们返回 [2,1] 。

说明：

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

思路

有一个数组 nums，求以每个元素为起点的子数组，取得最大或值的最小长度。res[i] 表示以 i 为起点的子数组中，数组元素按位或取得最大值时的最小长度。

枚举右端点，将当前元素与前面的元素进行或运算，并覆盖原来的元素值。对于当前元素 j，nums[i] 中存的是 i ~ j 的或值，站在集合的角度来看，nums[i + 1] 是 nums[i] 的子集。在进行或运算时，如果或值没有变大，就没有必要继续向前了。

代码

/**
 * @date 2025-07-29 9:39
 */
public class SmallestSubarrays2411 {

    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            res[i] = 1;
            for (int j = i - 1; j >= 0 && (num | nums[j]) != nums[j]; j--) {
                nums[j] |= num;
                res[j] = i - j + 1;
            }
        }
        return res;
    }

}

性能

目标

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]

示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]

说明：

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

思路

有一个正整数数组 nums，求一个不含重复元素的子数组，使得子数组的元素和最大。

滑动窗口，要求窗口内部不含重复元素，求窗口内元素和的最大值。

代码

/**
 * @date 2025-07-22 8:50
 */
public class MaximumUniqueSubarray1695 {

    public int maximumUniqueSubarray(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        int l = 0;
        int sum = 0;
        int res = 0;
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            while (l < r && set.contains(nums[r])) {
                sum -= nums[l];
                set.remove(nums[l++]);
            }
            set.add(nums[r]);
            res = Math.max(res, sum);
        }
        return res;
    }

}

性能

目标

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外。

示例 1：

输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]
输出：2
解释：
将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

示例 2：

输入：eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]
输出：6
解释：
将 [2, 4] 的会议安排到 [1, 3] ，得到空余时间 [3, 9] 。

示例 3：

输入：eventTime = 5, k = 2, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]
输出：0
解释：
活动中的所有时间都被会议安排满了。

说明：

• 1 <= eventTime <= 10^9
• n == startTime.length == endTime.length
• 2 <= n <= 10^5
• 1 <= k <= n
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

思路

有一个活动有 n 个时间不重叠的会议，重新安排 k 个会议议程，使得空余时间最大。

先根据会议时间排序，滑动窗口计算 k 个会议的总时间，以及 [end[l - 1], start[r + 1]]，相减即为窗口内的最大空余时间。

代码

/**
 * @date 2025-07-09 8:52
 */
public class MaxFreeTime3439 {

    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[][] interval = new int[n + 2][2];
        interval[0][1] = 0;
        for (int i = 1; i <= n; i++) {
            interval[i] = new int[]{startTime[i - 1], endTime[i - 1]};
        }
        interval[n + 1][0] = eventTime;
        int l = 1;
        int res = 0, sum = 0;
        for (int r = 1; r <= n; r++) {
            sum += interval[r][1] - interval[r][0];
            if (r - l == k - 1) {
                res = Math.max(res, interval[r + 1][0] - interval[l - 1][1] - sum);
                sum -= interval[l][1] - interval[l][0];
                l++;
            }
        }
        return res;
    }

}

性能

目标

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

}

性能