560. Subarray Sum Equals K

Problem Statement

Pattern: Pattern Prefix Array

---

Solution

public static int subArraySum(int[] nums, int k) {
	Integer count = 0, currSum = 0;
	Map<Integer, Integer> map = new HashMap<>();
	
	// edge case
	map.put(currSum, 1);
	
	for (int index = 0; index < nums.length; index++) {
		// update currSum at index
		currSum += nums[index];
		// get freq of currSum-k
		Integer freq = map.get(currSum - k);
		// if freq found update count
		if (freq != null) count += freq;
		// increment currSum freq
		map.put(currSum, map.getOrDefault(currSum, 0) + 1);
	}
	return count;
}

Notes

• In kadanes algo we know that

  • for a max sum problem
    • a negative currSum would never contribute to the a global max value
  • for a min sum problem
    • a positive currSum would never contribte to a global min value
  • so we reset currSum to the next element, and keep updating max and min

• Concept : update freq of currSum for each element in a hashmap

  • At any given index if map.get(currSum-k) let’s say is 2 that means, 2 subarrays with the sum k exist!!! only then would a sum = currSum-k would exist!
  • update the count with 2
  • so on…

• edge case, if currSum == k then map.get(0) should return 1.