AC第五天

Jie2025-04-142025-04-16

一. 不定长滑动窗口

不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，以及求子数组个数。

1. 求最长子数组

问题描述

在满足特定条件的情况下，找到最长的连续子数组的长度。

解题技巧

双指针法：使用两个指针（通常为 left 和 right）来表示当前窗口的左右边界。
扩展与收缩：
- 扩展窗口：移动 right 指针，增加窗口的大小，直到窗口内的元素不再满足条件。
- 收缩窗口：移动 left 指针，缩小窗口的大小，直到窗口内的元素重新满足条件。
记录最大长度：在每次满足条件时，更新记录的最大窗口长度。

示例

问题：给定一个整数数组和一个目标值 k，找到最长的子数组，使得子数组的和等于 k。

解题步骤：

初始化 left = 0，current_sum = 0，max_length = 0。
遍历数组，移动 right 指针：
- 将 nums[right] 加到 current_sum。
- 当 current_sum > k 时，移动 left 指针，并从 current_sum 中减去 nums[left]，直到 current_sum <= k。
- 如果 current_sum == k，更新 max_length = Math.max(max_length, right - left + 1)。
返回 max_length。

Java 代码示例

public class MaxSubarrayLen {
        public int maxSubarrayLen(int[] nums, int k) {
                int left = 0;
                int currentSum = 0;
                int maxLength = 0;
                for (int right = 0; right < nums.length; right++) {
                        currentSum += nums[right];
                        while (currentSum > k && left <= right) {
                                currentSum -= nums[left];
                                left++;
                        }
                        if (currentSum == k) {
                                maxLength = Math.max(maxLength, right - left + 1);
                        }
                }
                return maxLength;
        }
}

2. 求最短子数组

问题描述

在满足特定条件的情况下，找到最短的连续子数组的长度。

解题技巧

双指针法：同样使用 left 和 right 指针来表示窗口的边界。
扩展与收缩：
- 扩展窗口：移动 right 指针，直到窗口内的元素满足条件。
- 收缩窗口：一旦窗口满足条件，尝试移动 left 指针，尽可能缩小窗口的大小，同时仍满足条件，并记录最小的窗口长度。
记录最小长度：在每次满足条件时，更新记录的最小窗口长度。

示例

问题：给定一个整数数组和一个目标值 k，找到最短的子数组，使得子数组的和大于或等于 k。

解题步骤：

初始化 left = 0，current_sum = 0，min_length = ∞。
遍历数组，移动 right 指针：
- 将 nums[right] 加到 current_sum。
- 当 current_sum >= k 时，尝试缩小窗口：
  - 更新 min_length = Math.min(min_length, right - left + 1)。
  - 从 current_sum 中减去 nums[left]，并移动 left 指针向右。
返回 min_length（如果找到），否则返回 0。

Java 代码示例

public class MinSubarrayLen {
        public int minSubarrayLen(int[] nums, int k) {
                int left = 0;
                int currentSum = 0;
                int minLength = Integer.MAX_VALUE;
                for (int right = 0; right < nums.length; right++) {
                        currentSum += nums[right];
                        while (currentSum >= k) {
                                minLength = Math.min(minLength, right - left + 1);
                                currentSum -= nums[left];
                                left++;
                        }
                }
                return minLength != Integer.MAX_VALUE ? minLength : 0;
        }
}

3. 求子数组个数

问题描述

统计满足特定条件的连续子数组的总数。

解题技巧

滑动窗口：对于某些问题，滑动窗口仍然适用，尤其是当子数组具有重叠性质时。
前缀和与哈希表：更常见的是结合前缀和（Prefix Sum）与哈希表（Hash Map）来高效计算满足条件的子数组数量。
固定窗口大小 vs 可变窗口大小：
- 固定大小：窗口大小固定，可以直接遍历所有可能的窗口，统计满足条件的数量。
- 可变大小：需要根据条件动态调整窗口大小，通常结合前缀和与哈希表更为高效。

示例 1：固定窗口大小

问题：给定一个整数数组和一个整数 k，统计所有长度为 k 的子数组中，和为特定值 target 的数量。

解题步骤：

计算第一个窗口的和。
滑动窗口，每次移动时，减去移出的元素，加上新进入的元素，更新当前和。
如果当前和等于 target，计数加一。
返回总计数。

Java 代码示例

public class CountSubarraysFixed {
        public int countSubarraysFixed(int[] nums, int k, int target) {
                if (nums == null || nums.length < k) return 0;
                int currentSum = 0;
                for (int i = 0; i < k; i++) {
                        currentSum += nums[i];
                }
                int count = (currentSum == target) ? 1 : 0;
                for (int i = k; i < nums.length; i++) {
                        currentSum += nums[i] - nums[i - k];
                        if (currentSum == target) {
                                count++;
                        }
                }
                return count;
        }
}

示例 2：可变窗口大小

问题：给定一个整数数组和一个目标值 k，统计所有连续子数组的和等于 k 的数量。

解题技巧：

前缀和与哈希表：
- 计算前缀和 prefix_sum。
- 使用哈希表记录每个前缀和出现的次数。
- 对于当前前缀和 current_sum，查找 current_sum - k 是否存在于哈希表中，若存在，则累加相应的次数。
- 初始化哈希表时，{0: 1} 表示前缀和为 0 出现一次。

Java 代码示例

import java.util.HashMap;
import java.util.Map;

public class CountSubarraysVariable {
        public int countSubarraysVariable(int[] nums, int k) {
                Map<Integer, Integer> prefixCounts = new HashMap<>();
                prefixCounts.put(0, 1);
                int currentSum = 0;
                int count = 0;
                for (int num : nums) {
                        currentSum += num;
                        if (prefixCounts.containsKey(currentSum - k)) {
                                count += prefixCounts.get(currentSum - k);
                        }
                        prefixCounts.put(currentSum, prefixCounts.getOrDefault(currentSum, 0) + 1);
                }
                return count;
        }
}