Subarray Sum Equals K

return count of subArray with sum k

Subarray Sum Equals K

Problem

You are given an integer array nums and an integer k. Return the total number of subarrays whose sum is equal to k.

A subarray is a continuous, non-empty part of the array.

Examples

Example 1

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

• The subarray at index 0 to 1 is [1,1], and its sum is 2.
• The subarray at index 1 to 2 is [1,1], and its sum is 2.

Example 2

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

• [1,2] has sum 3.
• [3] has sum 3.

Constraints

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

Main Idea

Why sliding window does not work

The array can have negative numbers. So adding an element can make the sum smaller, and removing an element can make it bigger. We cannot move two pointers in one direction. We need another idea.

Prefix sums

A prefix sum at index i is the sum of all elements from index 0 to i.

The sum of a subarray from j + 1 to i is:

sum(j + 1 .. i) = prefix[i] - prefix[j]

We want this to be k:

prefix[i] - prefix[j] = k
prefix[j] = prefix[i] - k

So for each index i, we ask: "How many earlier prefix sums are equal to prefix[i] - k?" Each one gives one subarray that ends at i and has sum k.

We keep a hash map of prefix sums and how many times each one appeared.

Why start with {0: 1}? A subarray that starts at index 0 has no earlier prefix. It works as if there was a prefix sum of 0 before the array. So we save 0 once at the start.

Solution 1: Brute Force

We check every subarray. For each start index i, we move the end index j and keep a running sum.

var subarraySum = function (nums, k) {
    let count = 0;

    for (let i = 0; i < nums.length; i++) {
        let sum = 0;

        for (let j = i; j < nums.length; j++) {
            sum += nums[j];

            if (sum === k) {
                count++;
            }
        }
    }

    return count;
};

Note: I removed the console.log(sum) line from your code. It prints a lot of output and slows the code down.

How the Code Works

• The outer loop picks the start index i.
• The inner loop adds one element at a time, so sum is the sum of nums[i..j].
• Each time sum === k, we count one subarray.

Complexity

• Time Complexity: O(n²)
  • n is the length of the array.
  • We check every start and end pair.
  • With n = 2 * 10^4, this is about 2 * 10^8 steps, which is slow.
• Space Complexity: O(1)
  • We use only a few variables.

Note: The version with three nested loops, where the sum is calculated again for each subarray, takes O(n³). The running sum above removes the innermost loop.

Solution 2: Prefix Sum + Hash Map (Optimal)

function countSubarraysWithSumK(arr, k) {
    let count = 0;
    let prefixSum = 0;

    // Map to store the frequency of each prefix sum
    let map = new Map();

    // Important: handles subarrays that start at index 0
    map.set(0, 1);

    for (let i = 0; i < arr.length; i++) {
        prefixSum += arr[i];

        // the earlier prefix sum we need
        let remove = prefixSum - k;

        // each earlier match gives one subarray with sum k
        if (map.has(remove)) {
            count += map.get(remove);
        }

        // save the current prefix sum
        map.set(prefixSum, (map.get(prefixSum) || 0) + 1);
    }

    return count;
}

How the Code Works

Step 1: Set up

• count is the answer.
• prefixSum is the running sum from index 0 to i.
• map stores each prefix sum and how many times we saw it.
• map.set(0, 1) adds the empty prefix.

Step 2: Read each number

• We add arr[i] to prefixSum.
• remove = prefixSum - k is the earlier prefix sum that we need.

Step 3: Count the matches

• If remove is in the map, map.get(remove) tells us how many earlier positions have this prefix sum.
• Each of those positions is the start of a different subarray that ends at i and has sum k.
• So we add that number to count.

Step 4: Save the current prefix sum

• We update the map after the check. This way, the current prefix is not matched with itself. This matters when k = 0.

Dry Run

Let us take nums = [1, 2, 3] and k = 3.

The map starts as {0: 1}.

• At i = 1, the match with prefix 0 is the subarray [1,2].
• At i = 2, the match with prefix 3 is the subarray [3].

The answer is 2.

Now let us take a case with a negative number: nums = [1, -1, 1] and k = 1.

The answer is 3. The subarrays are [1], [1,-1,1] and the last [1].

Complexity

• Time Complexity: O(n)
  • We go through the array once.
  • Each map operation takes O(1) on average.
• Space Complexity: O(n)
  • In the worst case, every prefix sum is different, so the map holds n + 1 entries.

Comparison

Summary

• The array can have negative numbers, so sliding window does not work.
• The sum of a subarray is the difference of two prefix sums: prefix[i] - prefix[j].
• For each index, we look for earlier prefix sums equal to prefixSum - k.
• A hash map stores how many times each prefix sum appeared, so we find the count in O(1).
• We start the map with {0: 1}, so subarrays that begin at index 0 are counted.
• We update the map after the check, so a prefix is never matched with itself.
• The best solution runs in O(n) time and uses O(n) space.