Leetcode - Subarray Sum Equals K

Question

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.

Ideas

• This is basically glorified Leetcode - 2 Sum using Prefix Sums.
• We want to recognize that the subarray sum of any two indices is just subarraySum(i)-subarraySum(j)
  • [1, 2, 3, 4]
  • The sub array sum from j=2 to i =1 is 6 - 1 = 5
  • Using this idea, we can get the subarray sum for any index
  • The idea here is that we have our sub array sum at i and we know k, which means that we want some subarraySum[i]-subarraySum[j-1]=k which represents the sub array sum from j to i where j < i.
  • Rearranging this, we can see that subarraySum[j-1] = subarraySum[i]-k which means that given our current sum, and our target, we want to see if we have seen a given subarray sum before, if we have then increment res by its frequency that we are storing in a hash map, otherwise, set that mapping to 1

Solution