Medium

Subarray Sum Equals K

045

Given an integer array nums and an integer k, return the number of non-empty contiguous subarrays whose values sum to k.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    1,
    1
  ],
  "k": 2
}

Output
2

FUNCTION SHAPE

nums: intArrayk: int→int

SOLUTION NOTE

Brute force is O(n³) time O(1) space. You can get O(n²) using prefix sums. But this O(n) solution uses the Two Sum insight!

Why can we have multiple prefix sums with the same value? Because we allow 0's and negatives. Example: [3, 0, -1, 1] forms 3 prefix sums with value 3: ([3], [3,0], [3,0,-1,1])

Note: If the problem only allowed non-negative numbers, we could use a sliding window as an O(n) time and O(1) space solution.

Reveal reference solution +

pythonREFERENCE

def subarraySum(self, nums: List[int], k: int) -> int:
    prev_sum = Counter({0:1})  # sum -> frequency
    n, prefix_sum, res = len(nums), 0, 0

    for i in range(n):
        prefix_sum += nums[i]
        res += prev_sum[prefix_sum - k]
        prev_sum[prefix_sum] += 1

    return res

TimeO(n)

SpaceO(n)

Open on LeetCode ↗