Skip to content
Advertisement

JavaScript: return all contiguous subarrays whose sum equals K

This is a variant of this leetcode question, but instead of returning the count, we want to return the actual contiguous sub arrays. For example, if num = [1,2,4,7] k=7 the returned value should be [[1,2,4],[7]] .

I used a hashmap to store the cumulative sum up to all the indices possible along with the number of times the same sum occurs for the original question, where it asks to return the count

var subarraySum = function(nums, k) {
  let sum = 0;
  let count = 0;
  const myMap = new Map();
  myMap.set(0, 1);

  for (let num of nums) {
    sum += num;
    count += myMap.get(sum - k) || 0;
    myMap.set(sum, (myMap.get(sum) || 0) + 1);
  }
  
  return count;
}

But I cannot seem to figure out how I can adapt this solution to return the actual sub-arrays.

Advertisement

Answer

Below is an efficient solution with a minor tweak to the code your are referring to. This solution iterates over the input array once + whatever is required to add a subarray to the solution.

On the below line, you know the count if increases, you have something to add to your solution.

count += myMap.get(sum - k) || 0;

Now we need to understand at what index does sum - k exists in the map. On the below line, you are counting only the number of times the sum occurs.

myMap.set(sum, (myMap.get(sum) || 0) + 1);

Instead of just the count, you need to store the index* at which the sum occurs. Get rid of the counts throughout the code and focus only on index.

The pseudo code now looks like below:

for(int i = 0; i < nums.size(); i++):
    sum += nums[i]
    if(sum-k exists in the map):
        start_index = get the index corresponding to that sum-k
        //end_index will be the i
        add to the result set the subarray from start_index to i (or end_index)
    Set in map the sum and index i appropriately

*I hope the resultant subarrays don’t overlap. Otherwise, store a list of indices instead of an index.

Advertisement