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(N²)), 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(N²). 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)

Java

Go

```java public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> prevMap = new HashMap<>(); // val : index for (int i = 0; i < nums.length; i++) { int diff = target - nums[i]; if (prevMap.containsKey(diff)) { return new int[]{prevMap.get(diff), i}; } prevMap.put(nums[i], i); } return new int[]{}; } ```

```go func twoSum(nums []int, target int) []int { prevMap := make(map[int]int) // val : index for i, n := range nums { diff := target - n if prevIdx, exists := prevMap[diff]; exists { return []int{prevIdx, i} } prevMap[n] = i } return []int{} } ```

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?”

Java

Go

```java public int subarraySum(int[] nums, int k) { int res = 0; int curSum = 0; Map<Integer, Integer> prefixSums = new HashMap<>(); prefixSums.put(0, 1); // Base case: sum 0 occurs once (empty subarray) for (int n : nums) { curSum += n; int diff = curSum - k; res += prefixSums.getOrDefault(diff, 0); prefixSums.put(curSum, prefixSums.getOrDefault(curSum, 0) + 1); } return res; } ```

```go func subarraySum(nums []int, k int) int { res := 0 curSum := 0 prefixSums := map[int]int{0: 1} // Base case for _, n := range nums { curSum += n diff := curSum - k res += prefixSums[diff] prefixSums[curSum]++ } 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).

---