LeetCode LCR 010. 和为 K 的子数组

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 哈希表（推荐）
相似题目

题目描述

✅ LCR 010. 和为 K 的子数组

思路分析

解法一：前缀和 + 哈希表（推荐）

核心思路：

定义前缀和 pre[i] 为 nums[0..i] 的累加和，则子数组 nums[j+1..i] 的和 = pre[i] - pre[j]

若该子数组和等于 k，则 pre[j] = pre[i] - k，问题转化为：遍历到位置 i 时，历史上有多少个位置 j 满足 pre[j] = pre[i] - k

用哈希表记录每个前缀和出现的次数，边遍历边查询，实现 O(1) 查找

初始化 map[0] = 1：处理从数组头部开始的子数组，当 pre[i] == k 时，pre[i] - k = 0，需要有 1 个计数

本题不能用滑动窗口，因为数组中可能含有负数，窗口扩大不代表和单调增大，失去了双指针移动的前提

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，只需一次遍历

空间复杂度：O(n)，哈希表最多存储 n 个不同的前缀和

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 前缀和为 0 的情况出现 1 次，处理从头开始的子数组
        map.put(0, 1);
        int sum = 0;
        int count = 0;
        for (int num : nums) {
            sum += num;
            // 查询历史前缀和中有多少个满足 pre[j] = sum - k
            count += map.getOrDefault(sum - k, 0);
            // 将当前前缀和加入哈希表
            map.merge(sum, 1, Integer::sum);
        }
        return count;
    }
}

func subarraySum(nums []int, k int) int {
    // 初始化哈希表，前缀和为 0 出现 1 次
    prefixCount := map[int]int{0: 1}
    sum, res := 0, 0
    for _, num := range nums {
        sum += num
        // 累加满足 pre[j] = sum - k 的历史前缀和数量
        res += prefixCount[sum-k]
        // 记录当前前缀和出现次数
        prefixCount[sum]++
    }
    return res
}

相似题目

题目	难度	考察点
1. 两数之和	简单	哈希表查找差值
437. 路径总和 III	中等	前缀和 + DFS
523. 连续的子数组和	中等	前缀和 + 哈希表
525. 连续数组	中等	前缀和 + 哈希（0/1 转化）
974. 和可被 K 整除的子数组	中等	前缀和取模 + 哈希表
325. 和等于 k 的最长子数组长度	中等	前缀和 + 哈希（最长子数组）

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/43675801