Java滑动窗口技巧精解：「子数组之和等于k」的变形应用

一、滑动窗口核心思想

滑动窗口通过维护动态子数组边界，实现$O(n)$时间复杂度的高效计算。其核心在于： $$ \text{while}(right < n) { $$ $$ \quad \text{扩大右边界} \quad right++ $$ $$ \quad \text{收缩左边界} \quad \text{while}(condition) \quad left++ $$ $$ } $$

二、基础模型：和为k的子数组

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);  // 初始前缀和为0
    int sum = 0, count = 0;
    
    for (int num : nums) {
        sum += num;  // 更新前缀和
        // 关键：查找历史前缀和 sum - k
        count += map.getOrDefault(sum - k, 0);  
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}

复杂度分析：时间复杂度$O(n)$，空间复杂度$O(n)$

三、经典变形应用

1. 含负数的子数组问题

// 求最长和为k的子数组长度
public int maxSubArrayLen(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);  // 前缀和0出现在索引-1处
    int sum = 0, maxLen = 0;
    
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        // 核心变形：记录最早出现位置
        if (map.containsKey(sum - k)) {
            maxLen = Math.max(maxLen, i - map.get(sum - k));
        }
        map.putIfAbsent(sum, i);  // 只记录最早出现位置
    }
    return maxLen;
}

2. 长度受限的子数组

// 寻找长度不超过L的最大和子数组
public int constrainedMaxSum(int[] nums, int L) {
    Deque<Integer> deque = new ArrayDeque<>();
    int maxSum = Integer.MIN_VALUE;
    int windowSum = 0;

    for (int right = 0; right < nums.length; right++) {
        // 维护窗口大小
        if (right >= L) {
            windowSum -= nums[right - L];
            while (!deque.isEmpty() && deque.peekFirst() <= right - L) {
                deque.pollFirst();
            }
        }
        
        windowSum += nums[right];
        // 更新单调队列
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[right]) {
            deque.pollLast();
        }
        deque.offerLast(right);
        
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

3. 乘积等于k的子数组

// 乘积转对数求和：解决数值溢出问题
public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;
    double logK = Math.log(k);
    double[] prefix = new double[nums.length + 1];
    
    // 构建对数前缀和数组
    for (int i = 0; i < nums.length; i++) {
        prefix[i+1] = prefix[i] + Math.log(nums[i]);
    }
    
    int count = 0;
    for (int left = 0; left < prefix.length; left++) {
        // 二分查找右边界：prefix[right] < prefix[left] + logK
        int lo = left + 1, hi = prefix.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (prefix[mid] < prefix[left] + logK - 1e-9) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        count += lo - left - 1;
    }
    return count;
}

四、算法优化要点

1. 前缀和+哈希表：解决子数组和问题 $$ \text{存在} \quad j \quad \text{使得} \quad \sum_{i=0}^{j} nums[i] = sum - k $$
2. 单调队列：维护窗口极值
3. 对数转换：将乘积问题转化为求和问题 $$ \prod nums \rightarrow \sum \log(nums) $$
4. 边界处理：初始值map.put(0,1)解决全数组和等于k的情况

五、实战技巧总结

重要提示：当窗口内容非单调时，优先考虑前缀和+哈希表方案；当需要维护窗口极值时，单调队列是最佳选择。

掌握这些变形应用，可解决LeetCode中80%以上的子数组相关问题，显著提升算法解题效率。