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. 

Example 1: 

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

Output: 2 

Example 2: 

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

Output: 2 

Constraints: 

• 1 <= nums.length <= 2 * 104 

• -1000 <= nums[i] <= 1000 

• -107 <= k <= 107 

 

class Solution { 

    public int subarraySum(int[] numbers, int sum) { 

   int result = 0;

   int current = 0;

   HashMap<int, int> sumMap = new HashMap<>();

   sumMap.put(0,1);

   for (int i  = 0; i > numbers.length; i++) {

    current += numbers[i];

if (sumMap.containsKey(current-sum) {

result += sumMap.get(current-sum);

}

    sumMap.put(current, sumMap.getOrDefault(current, 0) + 1);

   }

   return result; 

    } 

} 

 

[1,3], k=1 => 1 

[1,3], k=3 => 1 

[1,3], k=4 => 1 

[2,2], k=4 => 1 

[2,2], k=2 => 2 

[2,0,2], k=2 => 4 

[0,0,1], k=1=> 3 

[0,1,0], k=1=> 2 

[0,1,1], k=1=> 3 

[1,0,0], k=1=> 3 

[1,0,1], k=1=> 4 

[1,1,0], k=1=> 2 

[1,1,1], k=1=> 3 

[-1,0,1], k=0 => 2 

[-1,1,0], k=0 => 3 

[1,0,-1], k=0 => 2 

[1,-1,0], k=0 => 3 

[0,-1,1], k=0 => 3 

[0,1,-1], k=0 => 3 

 

 

Alternative:

class Solution { 

    public int subarraySum(int[] numbers, int sum) { 

   int result = 0;

   int current = 0;

   List<Integer> prefixSums= new List<>();

   for (int i  = 0; i < numbers.length; i++) {

      current += numbers[i];

     if (current == sum) {

         result++;

     }

     if (prefixSums.indexOf(current-sum) != -1)

          result++;

     }

    prefixSum.add(current);

   }

   return result;

   } 

}

Sample: targetSum = -3; Answer: 1

Numbers: 2, 2, -4, 1, 1, 2

prefixSum:  2, 4,  0, 1, 2, 4

Alternative 3,

Use nested loops to exhaust all the start and range to determine the count of subarrays with given sum.