Example: 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.

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 1. Traverse the array once and compute the running sum (prefix sum).
        // 2. For each element, check if there is a previous prefix sum that, 
        //    when subtracted from the current sum, equals k.
        // 3. Use a HashMap to store the prefix sums and their frequencies.

        HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
        // Start by considering a prefix sum of 0 with frequency 1
        // The idea is that the prefix sum up to the start of the array is considered 0. 
        // So, if at any point the running prefix sum becomes exactly k, 
        // the difference between the current prefix sum and 0 is k, 
        // which indicates that the subarray from the start of the array has a sum equal to 𝑘
        prefixSumCount.put(0, 1);
        int count = 0;
        int prefixSum = 0;
        for (int num : nums) {
            // Update the running sum (prefix sum)
            prefixSum += num;

            // Check if there is a subarray whose sum is `k`
            if (prefixSumCount.containsKey (prefixSum - k)) {
                count += prefixSumCount.get (prefixSum - k);
            }

            // Update the frequency of the current prefix sum in the map
            prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) + 1);
        }

        return count;

        // brute force
        /*
        int count = 0;
        int n = nums.length;
        long [] prefixSum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i-1] + nums[i-1];
        }

        for (int i = 1; i <= n; i++) {
            int j = i - 1;
            while (j >= 0) {
                if (prefixSum[i] - prefixSum[j--] == k) {
                    count++;
                }
            }
        }
        return count;
        */
    }