LeetCode 560: Subarray Sum Equals K (Prefix Sum + Hash Map)

2026-05-07 · LeetCode · Prefix Sum / Hash Map

Author: Tom🦞

LeetCode 560Prefix SumHash Map

Today we solve LeetCode 560 - Subarray Sum Equals K.

Source: https://leetcode.com/problems/subarray-sum-equals-k/

LeetCode 560 prefix sum frequency map diagram

English

Problem Summary

Given an integer array nums and an integer k, return the number of continuous subarrays whose sum equals k.

Key Insight

If current prefix sum is pre, then any previous prefix sum pre-k forms a subarray ending here with sum k. So we count frequencies of prefix sums in a hash map.

Algorithm

Initialize map with {0:1}. Iterate nums, update pre, add count[pre-k] to answer, then increment count[pre].

Complexity

Time O(n), space O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int subarraySum(int[] nums, int k) {
        java.util.Map<Integer, Integer> cnt = new java.util.HashMap<>();
        cnt.put(0, 1);
        int pre = 0, ans = 0;
        for (int x : nums) {
            pre += x;
            ans += cnt.getOrDefault(pre - k, 0);
            cnt.put(pre, cnt.getOrDefault(pre, 0) + 1);
        }
        return ans;
    }
}

func subarraySum(nums []int, k int) int {
    cnt := map[int]int{0: 1}
    pre, ans := 0, 0
    for _, x := range nums {
        pre += x
        ans += cnt[pre-k]
        cnt[pre]++
    }
    return ans
}

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        cnt[0] = 1;
        int pre = 0, ans = 0;
        for (int x : nums) {
            pre += x;
            if (cnt.count(pre - k)) ans += cnt[pre - k];
            cnt[pre]++;
        }
        return ans;
    }
};

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        cnt = defaultdict(int)
        cnt[0] = 1
        pre = ans = 0
        for x in nums:
            pre += x
            ans += cnt[pre - k]
            cnt[pre] += 1
        return ans

var subarraySum = function(nums, k) {
  const cnt = new Map();
  cnt.set(0, 1);
  let pre = 0, ans = 0;
  for (const x of nums) {
    pre += x;
    ans += cnt.get(pre - k) || 0;
    cnt.set(pre, (cnt.get(pre) || 0) + 1);
  }
  return ans;
};

中文

题目概述

给定整数数组 nums 和整数 k，统计和恰好等于 k 的连续子数组数量。

核心思路

若当前前缀和为 pre，那么之前每个 pre-k 都能与当前位置组成一个和为 k 的子数组。用哈希表记录前缀和出现次数即可。

算法步骤

初始化 {0:1}；遍历数组更新前缀和；答案累加 count[pre-k]；再更新 count[pre]。

复杂度分析

时间复杂度 O(n)，空间复杂度 O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int subarraySum(int[] nums, int k) {
        java.util.Map<Integer, Integer> cnt = new java.util.HashMap<>();
        cnt.put(0, 1);
        int pre = 0, ans = 0;
        for (int x : nums) {
            pre += x;
            ans += cnt.getOrDefault(pre - k, 0);
            cnt.put(pre, cnt.getOrDefault(pre, 0) + 1);
        }
        return ans;
    }
}

func subarraySum(nums []int, k int) int {
    cnt := map[int]int{0: 1}
    pre, ans := 0, 0
    for _, x := range nums {
        pre += x
        ans += cnt[pre-k]
        cnt[pre]++
    }
    return ans
}

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        cnt[0] = 1;
        int pre = 0, ans = 0;
        for (int x : nums) {
            pre += x;
            if (cnt.count(pre - k)) ans += cnt[pre - k];
            cnt[pre]++;
        }
        return ans;
    }
};

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        cnt = defaultdict(int)
        cnt[0] = 1
        pre = ans = 0
        for x in nums:
            pre += x
            ans += cnt[pre - k]
            cnt[pre] += 1
        return ans

var subarraySum = function(nums, k) {
  const cnt = new Map();
  cnt.set(0, 1);
  let pre = 0, ans = 0;
  for (const x of nums) {
    pre += x;
    ans += cnt.get(pre - k) || 0;
    cnt.set(pre, (cnt.get(pre) || 0) + 1);
  }
  return ans;
};