Subarray Sum Equals K

LeetCode 560 | Difficulty: Medium

Medium

Problem Description

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.

Example 1:

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

Example 2:

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

Constraints:

- `1 <= nums.length <= 2 * 10^4`

- `-1000 <= nums[i] <= 1000`

- `-10^7 <= k <= 10^7`

Topics: Array, Hash Table, Prefix Sum

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 136 ms)

Metric	Value
Runtime	136 ms
Memory	44.8 MB
Date	2021-12-02

Solution

public class Solution {
    public int SubarraySum(int[] nums, int k)
    {
    int n= nums.Length;
    Dictionary<int, int> counts = new Dictionary<int, int>();
    counts.Add(0,1);
    var sum = 0;
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        sum += nums[i];
        if(counts.ContainsKey(sum-k))
        {
            result += counts[sum-k];            
        }
        if(counts.ContainsKey(sum))
        {
            counts[sum]++;
        }
        else
        {
            counts.Add(sum, 1);
        }
    }
    
    return result;  
}
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Will Brute force work here? Try to optimize it.

Hint 2: Can we optimize it by using some extra space?

Hint 3: What about storing sum frequencies in a hash table? Will it be useful?

Hint 4: sum(i,j)=sum(0,j)-sum(0,i), where sum(i,j) represents the sum of all the elements from index i to j-1.

Can we use this property to optimize it.