Explorer
Data Structures & Algorithms

Find the total number of continuous subarrays whose sum equals k.

Problem Statement

Given an array of integers `nums` and an integer `k`, return the total number of subarrays whose sum equals to `k`.

Examples

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

Output: 2

Explanation: Combining the input according to Count subarrays with given sum logic yields 2.

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

Output: 2

Explanation: Combining the input according to Count subarrays with given sum logic yields 2.

Input: nums = [3, 1, 2, 4], k = 6

Output: 2

Explanation: Combining the input according to Count subarrays with given sum logic yields 2.

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

Hints

šŸ’” Hint 1: Use a prefix sum hash map to store frequencies of seen cumulative sums. šŸ’” Hint 2: Base case: prefixMap.set(0, 1) represents a prefix sum of 0 occurring before index 0. šŸ’” Hint 3: At each step, add prefixMap.get(currentSum - k) to the count, then increment frequency of currentSum.

Editorial & Approach

Problem Overview & Intuition

If the cumulative sum up to index i is S, any previous prefix sum equal to S - K defines a valid contiguous subarray ending at i that sums to K. Storing frequencies in a Map allows answering each step in O(1).

Step-by-Step Approach

  1. Initialize count = 0, currentSum = 0, and prefixMap = new Map([[0, 1]]).
  2. Iterate through num in nums.
  3. Accumulate currentSum += num.
  4. If prefixMap.has(currentSum - k), add its frequency to count.
  5. Increment frequency of currentSum in the map.
  6. Return count.

Optimal Implementation (JavaScript)

function subarraySum(nums, k) {
  let count = 0, currentSum = 0;
  const prefixMap = new Map();
  prefixMap.set(0, 1);

  for (let num of nums) {
    currentSum += num;
    if (prefixMap.has(currentSum - k)) {
      count += prefixMap.get(currentSum - k);
    }
    prefixMap.set(currentSum, (prefixMap.get(currentSum) || 0) + 1);
  }

  return count;
}

Complexity Analysis

Time Complexity O(N) ā€” single pass with O(1) hash map operations.
Space Complexity O(N) ā€” hash map storing prefix sum frequencies.

Edge Cases & Corner Traps Handled

  • k is negative.
  • Array with multiple zeroes, giving multiple ways to form sum k.
  • No valid subarray exists (returns 0).

Count subarrays with given sum

Medium
Given an array of integers `nums` and an integer `k`, return the total number of subarrays whose sum equals to `k`.
Example Scenarios
1Example 1
Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation:

Combining the input according to Count subarrays with given sum logic yields 2.

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

Combining the input according to Count subarrays with given sum logic yields 2.

3Example 3
Input: nums = [3, 1, 2, 4], k = 6
Output: 2
Explanation:

Combining the input according to Count subarrays with given sum logic yields 2.

Editor
Loading Editor...
nums =
[1, 1, 1]
k =
2
Output:Click "Run" above to execute and verify your code here.
2