# Subarray Sum Equals k

## # Solution

The brute force solution would:

• enumerate subarrays in a nested for loop ()
• calculate sum in a for loop ()
• update if current subarray has largest sum ()

So in total takes time.

### # Squared Time Solutions

The following two time solutions would TLE in Python but might pass in other languages, such as C++ and Java.

#### # Prefix Sum (TLE)

Calculate prefix sum in time beforehand, so that csum can be obtained in time.

Complexity:

• time:
• space:
def subarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
cnt = 0

prefix_sum = [0]*n
prefix_sum[0] = nums[0]
for i in range(1,n):
prefix_sum[i] = prefix_sum[i-1] + nums[i]

for i in range(n):
for j in range(i,n):
if i==0:
csum = prefix_sum[j]
else:
csum = prefix_sum[j] - prefix_sum[i-1]
if csum==k:
cnt += 1
return cnt


#### # Cumulative Sum (TLE)

Calculate csum cumulatively.

Complexity:

• time:
• space:
def subarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
cnt = 0
for i in range(n):
csum = 0
for j in range(i,n):
csum += nums[j]
if csum==k:
cnt += 1
return cnt


### # HashMap (linear time)

If nums[i] summing to nums[j] equals k, prefix_sum[i] == prefix_sum[j] - k, then we just need to find if satisfying prefix_sum[i] has occurred. If so, increase count by occurrences of prefix_sum[i]. Use a HashMap to store mappings from prefix sum to occurrence.

The following three solutions are all from this post. The last two using Counter are a bit of overhaul and vanilla HashMap is good enough.

Complexity:

• time:
• space:

#### # Vanilla HashMap

def subarraySum(self, nums, k):
hm, csum, res = {0: 1}, 0, 0
for num in nums:
csum += num
res += hm.get(csum - k, 0)
hm[csum] = hm.get(csum, 0) + 1
return res

Counter & Accumulate

#### # Counter

Use Counter from collections as a shorthand.

def subarraySum(self, A, K):
count = collections.Counter()
count[0] = 1
ans = su = 0
for x in A:
su += x
ans += count[su-K]
count[su] += 1
return ans


#### # Accumulate

from collections import Counter
from itertools import accumulate

def subarraySum(nums, k):
total = 0
count = Counter()
count[0] += 1
for acc in accumulate(nums):
total += count[acc - k]
count[acc] += 1