Subarray Sum TwoSum

This pattern solves a huge class of problems: “Find two elements that combine to form a Target”. Instead of checking every pair (O(N2)), we use a Hash Map to “remember” what we’ve seen so far, allowing us to find the complement in O(1).

Problem 1: Two Sum (LeetCode 1)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Brute Force: Check every pair. O(N2). Hash Map:

  1. As we iterate through x, we need y such that x + y = target.
  2. Rewrite: y = target - x.
  3. Check if y is already in our map.

Interactive Visualizer

Step through the algorithm to see how the map helps us find the answer in one pass.

Two Sum Explorer

Ready to start.
HASH MAP (Val → Index)
def twoSum(nums, target):
  prevMap = {} # val : index

  for i, n in enumerate(nums):
    diff = target - n
    if diff in prevMap:
      return [prevMap[diff], i]
    prevMap[n] = i
  return []

Problem 2: Subarray Sum Equals K (LeetCode 560)

Given an array nums and integer k, find the total number of continuous subarrays whose sum equals k.

The Logic: The sum of a subarray nums[i...j] is PrefixSum[j] - PrefixSum[i-1]. We want this to equal k. PrefixSum[j] - PrefixSum[i-1] = k Rearranging: PrefixSum[i-1] = PrefixSum[j] - k

So, as we iterate and calculate the running sum (current<sub>sum</sub>), we check: “How many times have I seen a prefix sum equal to current<sub>sum</sub> - k?”

def subarraySum(nums, k):
  res = 0
  curSum = 0
  prefixSums = {0: 1} # Base case: sum 0 occurs once (empty subarray)

  for n in nums:
    curSum += n
    diff = curSum - k

    res += prefixSums.get(diff, 0)

    prefixSums[curSum] = 1 + prefixSums.get(curSum, 0)

  return res

Example Walkthrough

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

  1. Init: prefixSums = {0: 1}, res = 0, curSum = 0
  2. i=0, n=1:
    • curSum = 1
    • diff = 1 - 2 = -1 (Not in map)
    • Add 1 to map: {0: 1, 1: 1}
  3. i=1, n=1:
    • curSum = 2
    • diff = 2 - 2 = 0 (Found 1 in map!) → res += 1
    • Add 2 to map: {0: 1, 1: 1, 2: 1}
  4. i=2, n=1:
    • curSum = 3
    • diff = 3 - 2 = 1 (Found 1 in map!) → res += 1
    • Add 3 to map: {0: 1, 1: 1, 2: 1, 3: 1}

Result: 2. (Subarrays: [1, 1] at start, [1, 1] at end).

Deep Dive Strategy Lab: Subarray Sum Twosum

Intuition Through Analogy

Think of this chapter like library card catalog lookup. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?