Skip to content

560. Subarray Sum Equals K

Intitution

To find the number of subarrays whose sum is equal to k, we can use the concept of prefix sums.\ If the sum of elements from index i to j is k, then:

CopyEditprefixSum[j + 1] - prefixSum[i] = k

Rearranging:

CopyEditprefixSum[i] = prefixSum[j + 1] - k

So, for each prefix sum encountered, we want to know how many times (currentPrefixSum - k) has appeared before.\ This is efficiently done using a hash map to track prefix sum frequencies.

Complexity

Space Complexity Time Complexity
$\(\text{O}(N)\)$ $\(\text{O}(N)\)$

Code

public int subarraySum(int[] nums, int k) {
    int[] prefixSumArray = new int[nums.length + 1];

    // Step 1: Compute prefix sums
    for (int i = 1; i < prefixSumArray.length; ++i) {
        prefixSumArray[i] = prefixSumArray[i - 1] + nums[i - 1];
    }

    int subarrayCount = 0;

    // Step 2: Map to store frequency of prefix sums
    Map<Integer, Integer> prefixSumFrequency = new HashMap<>();

    for (int i = 0; i < prefixSumArray.length; ++i) {
        int currentPrefixSum = prefixSumArray[i];
        int requiredPrefixSum = currentPrefixSum - k;

        // If requiredPrefixSum has been seen before, it contributes to the count
        if (prefixSumFrequency.containsKey(requiredPrefixSum)) {
            subarrayCount += prefixSumFrequency.get(requiredPrefixSum);
        }

        // Update the frequency of the current prefix sum
        prefixSumFrequency.put(currentPrefixSum, prefixSumFrequency.getOrDefault(currentPrefixSum, 0) + 1);
    }

    return subarrayCount;
}

Comments