560. Subarray Sum Equals K

/*
Given an array of integers and an integer k,
you need to find the total number of continuous subarrays whose sum equals to k.

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

Idea:
Postfix sums: [1,2,3] -> [0,1,3,6].
k = sum(i,j) =  postixSum[j + 1] - postfixSum[i] => postfixSum[i] = postfixSum[j + 1] - k.

postfixSum[j + 1] = sum of nums from 0 to j
*/

class SimpleSolution {
    public int subarraySum(int[] nums, int k) {
        int counter = 0;
        
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if(sum == k){
                    counter++;
                }
            }
        }
        
        return counter;
    }
}

class HashMapSolution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> foundedSumsMap = new HashMap<>();
        foundedSumsMap.put(0, 1);

        int counter = 0;
        int postfixSum = 0;
        for (int i = 0; i < nums.length; i++) {
            postfixSum += nums[i];
            //k = sum(i,j) =  postixSum[j + 1] - postfixSum[i] => postfixSum[i] = postfixSum[j + 1] - k.
            if (foundedSumsMap.containsKey(postfixSum - k)) {
                counter += foundedSumsMap.get(postfixSum - k);
            }
            foundedSumsMap.put(postfixSum, foundedSumsMap.getOrDefault(postfixSum, 0) + 1);
        }

        return counter;
    }
}