LeetCode 补拙笔记

0. 前言

• 日期：2026.06.28
• 题目：560. 和为 K 的子数组
• 难度：中等
• 标签：前缀和、哈希表、数组

1. 题目理解

问题描述 给定整数数组 nums 和整数 k，统计数组中连续非空子数组元素之和等于 k 的子数组总数量。

示例

输入：nums = [1,1,1], k = 2 输出：2 解释：子数组 [0,1]、[1,2] 总和都等于 2，共2个。

2. 解题思路

核心观察

1. 定义前缀和 pre[i]：nums[0] ~ nums[i] 全部元素累加和；
2. 区间 [j+1, i] 的和 = pre[i] - pre[j]，要求该值等于 k，等价于寻找 pre[j] = pre[i] - k；
3. 使用哈希表存储此前所有前缀和出现的次数，遍历到 pre[i] 时直接累加符合条件的 pre[j] 数量；
4. 初始哈希表存入 {0:1}，用来处理 pre[i] == k 的边界情况，消除单独判断分支。

算法步骤

1. 初始化哈希表，存入前缀和0，出现次数1；
2. 遍历数组，实时维护当前前缀和；
3. 计算目标值 curSum - k，若哈希表存在该值则累加对应次数；
4. 将当前前缀和更新存入哈希表；
5. 遍历结束返回总计数。

3. 代码实现

package lc560;

import java.util.HashMap;

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0;
        int n = nums.length;
        int[] pre = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        pre[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pre[i] = nums[i] + pre[i - 1];
        }
        for (int i = 0; i < n; i++) {
            if (pre[i] == k) {
                res++;
            }
            int need = pre[i] - k;
            if (map.containsKey(need)) {
                res += map.get(need);
            }
            map.put(pre[i], map.getOrDefault(pre[i], 0) + 1);
        }
        return res;
    }
}

4. 代码优化说明

import java.util.HashMap;
class Solution {
public int subarraySum(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap<>();
    // 初始前缀和0出现1次，直接覆盖pre[i]==k场景，消除if判断
    map.put(0, 1);
    int curSum = 0, ans = 0;
    for (int num : nums) {
        curSum += num;
        int target = curSum - k;
        // getOrDefault替代containsKey分支判断，不存在时直接取0
        ans += map.getOrDefault(target, 0);
        map.put(curSum, map.getOrDefault(curSum, 0) + 1);
    }
    return ans;
}
}

5. 复杂度分析

• 原版前缀和数组版本 时间复杂度：$O(n)$，两次线性遍历数组，存在两处if条件分支 空间复杂度：$O(n)$，额外开辟前缀和数组与哈希表
• 优化版一维遍历 时间复杂度：$O(n)$，仅单次遍历数组，删除多余条件分支 空间复杂度：$O(n)$，取消前缀和数组，仅保留哈希表存储前缀和频次

6. 总结

• 核心：前缀和公式转换 pre[i] - pre[j] = k，用哈希表统计历史前缀和频次；
• 优化亮点：
  1. 初始化 map.put(0,1) 消除 pre[i]==k 的独立if判断；
  2. 实时累加curSum，取消存储全部前缀和的数组，节省空间；
  3. getOrDefault 替代 containsKey 多层分支，代码更简洁；
• 关键：子数组连续的特性是前缀和算法成立的前提。