Skip to main content

560. Subarray Sum Equals K

medium

Count the contiguous subarrays whose sum equals k. The textbook prefix-sum + hash-map combo — the moment 'subarray sum' shows up in any prompt, this pattern should fire instantly.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

Examples

Example 1

Input
nums = [1,1,1], k = 2
Output
2

Example 2

Input
nums = [1,2,3], k = 3
Output
2

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force checks every (i, j) pair — O(n^2). What invariant lets you reduce it to a single pass?

Hint 2

Prefix sums: sum(nums[i..j]) = prefix[j] - prefix[i-1]. So sum == k iff prefix[j] - prefix[i-1] == k iff prefix[i-1] == prefix[j] - k.

Hint 3

Walk the array tracking prefix sum and a hash map of {prefix-sum-so-far -> count of times it's appeared}. For each step, add map[prefix - k] to the answer. Start map with {0: 1} to handle subarrays starting at index 0.

Solution approach

Reveal approach

Prefix sum + hash map. Initialize prefix_count = {0: 1} (the empty prefix has sum 0, count 1 — this handles subarrays that start at index 0). Walk nums, maintaining a running prefix sum. At each step, look up prefix_count[prefix - k]: that's the count of past prefixes such that their gap to the current prefix equals k, i.e., subarrays ending here with sum k. Add it to the result counter. Then increment prefix_count[prefix]. The {0: 1} seed is the easy-to-forget detail; without it you miss any subarray whose prefix equals k itself. O(n) time, O(n) space.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • prefix-sum
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Subarray Sum Equals K and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →