Arrays - Subarray Sum Equals K

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.

Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation:
one contiguous subarray is from index 0-1 [1, 1]
second contiguous subarray is from index 1-2 [1, 1]

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

Input: nums = [1, -1, 1], k = 1
Output: 3
Explanation:
one contiguous subarray at index 0 [1]
second contiguous subarray is from index 0-2 [1, -1, 1]
third contiguous subarray at index 2 [1]

Constraints:

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

Solution 1 - Create prefix sum array and then find if there is a possible continuous subarray with K sum

As per the problem statement, one of the key point to remember is that the input array can contain negative numbers, so we have to find continuous subarrays that includes negative numbers too for example if the k=1 and input array is [1, -1, 1] then subarrays with [1] as well as [1, -1, 1] will give sum of 1.

In this approach, we will first compute a prefix sum array, then we create a HashMap to store the mapping of prefix - k to it's count of how many times have this number appeared and if the number appeared add it to the result.
The main idea is if we find the prefix -k in the map that means there is a subarray from the index where this found (exclusive) and the current prefix.

Example:

Lets look at an example with input array [1, 2, 3, 4, 5] and k = 9, by looking at the aray we can see there are two contiguous subarrays [2, 3, 4] and [4, 5], let's apply the steps on this input.

First, lets compute the prefix sum array using: preffixSum[i] = nums[i] + (i==0 ? 0 : preffixSum[i-1]); So, the prefix sum array will be [1, 3, 6, 10, 15]
Next, we will create a HashMap to store prefix -k and store the count as 1, or if it already exists then increment the count.
- If we find prefix -k in the array, that means the sub array where the index of this value started (exclusive), and until the current prefix it is a contiguous subarray. In the above example, at index 3 in prefix sum we have value 10 so prefix-k will be 1 and this value is at index 0, so that means there is a sub array from index 1 to index 3 in the original array. [2, 3, 4]
- Similarly, at index at index 4 in prefix sum we have value 15 so prefix-k will be 6 and this value is at index 2, so that means there is a sub array from index 3 to index 4 in the original array. [4, 5]
Also, store 0 as key and 1 as value, because, if the sum k starts from index 0. The reason we need to do this is because, if the sum k includes the 0^th index in input array, for example nums = [1, -1, 1] and k=1, here first element in array is 1, and k- prefix will be 0. So, to account this we will store with 0, there will be always 1 answer.

import java.util.HashMap; public class SubarraysSumEqualToK { static int subarraySum(int[] nums, int k) { int result = 0; int[] prefixSum = new int[nums.length]; prefixSum[0] = nums[0]; for(int i=1; i<nums.length; i++) { prefixSum[i] = nums[i] + prefixSum[i-1]; } HashMap<Integer, Integer> map = new HashMap<>(); map.put(0, 1); for(int prefix: prefixSum) { if(map.containsKey(prefix-k)) { result += map.get(prefix-k); } map.merge(prefix, 1, Integer::sum); } System.out.println(map); return result; } public static void main(String[] args) { System.out.println(subarraySum(new int[]{1,-1,1}, 1)); System.out.println(subarraySum(new int[]{1,2,3,4,5}, 9)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(n), since we are creating prefix sum array with size n and a HashMap to keep the counts.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Example:

Complexity Analysis: