Simple example
Input
nums = [1, 1, 1], k = 2
Output
2
Subarrays [1,1] at positions (0,1) and (1,2) each sum to 2.
Full lesson preview
Count Subarrays with Sum k by Brute Force
Count the number of contiguous subarrays whose elements sum to a target k using an efficient approach.
Python practice30 minArrays – Fundamentals & PatternsAdvancedLast updated March 25, 2026
Problem statement
Given an array of integers nums and an integer k, return the number of contiguous subarrays whose sum equals k. The naive O(n^2) approach checks all subarrays; here you'll use prefix sums and a hashmap to achieve O(n) time and O(n) extra space. Consider negative numbers and zeros as well.
Task
Implement an O(n) algorithm using prefix sums and a hashmap to count subarrays summing to k.
Examples
Input format
Two arguments: a list of integers nums and an integer k. Example: count_subarrays_with_sum([1,2,3], 3)
Output format
Integer representing the count of contiguous subarrays whose sum equals k.
Constraints
0 <= len(nums) <= 10^5. -10^9 <= nums[i], k <= 10^9. Aim for O(n) time and O(n) extra space.
Samples
Sample 1
Input
nums = [1, -1, 0], k = 0
Output
3
Subarrays [1,-1], [0], and [1,-1,0] sum to 0.