Subarray Sum Equals K

MEDIUM✓ CHIP-TIMEDLC #560 — FULL STATEMENT ↗

The drill: Count how many contiguous stretches of an array add up exactly to a target sum — overlapping stretches all count separately, and negative numbers keep things honest.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers and a target sum k arrive together, and the task is counting how many contiguous stretches of the array add up to exactly k.

Stretches are free to overlap each other, and every distinct starting-and-ending pair that hits the target counts separately, even if two stretches share most of their elements.

Negative numbers are allowed throughout the array, which means a running total can rise and fall unpredictably — a stretch summing to k doesn't require every element inside it to be positive.

EX 01

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

→ 2

TWO OVERLAPPING PAIRS BOTH SUM TO 2

EX 02

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

→ 2

ONE PREFIX PAIR AND ONE SINGLETON BOTH HIT 3

EX 03

nums = [1, -1, 0] · k = 0

→ 3

ZERO TARGET, MIX OF CANCELLATION AND A LITERAL ZERO

arrays can hold up to several thousand elements
values and k may be negative, zero, or positive
overlapping subarrays are counted separately, every valid stretch counts
the answer is a single integer count, zero when no stretch matches

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Recomputing the sum of every stretch from scratch wastes work — what relationship connects the sum of two stretches that share the same starting point at index 0?

HINT 2 THE STRUCTURE

A stretch's sum is the difference of two running totals: sum(i..j) = runningSum(j) − runningSum(i − 1). If that difference equals k, then runningSum(i − 1) is a value you've already seen — so the question becomes how many times you've seen it.

HINT 3 ONE STEP FROM THE ANSWER

Walk once with a running sum and a map from running-sum value to how many times it's occurred so far. At each step, add whatever count is stored under (runningSum − k) to your answer, then record the current running sum in the map — seed the map with {0: 1} so a stretch starting at index 0 can match too.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE PREFIX PASSPATTERN · PREFIX SUM + HASH MAPnums = [1, 1, 1] · k = 2

THE MAP — RUNNING SUM → COUNT

0 → 1

STEP 1

Target k = 2. Seed the map with running sum 0 seen once, so a stretch starting at index 0 can match too.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/subarray-sum-equals-k.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        seen = {0: 1}                   # running-sum value -> how many times it's occurred
        running = 0
        count = 0
        for v in nums:
            running += v
            count += seen.get(running - k, 0)
            seen[running] = seen.get(running, 0) + 1
        return count

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 10 LN

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count = 0
        for i in range(n):
            total = 0
            for j in range(i, n):       # expand the stretch one element at a time
                total += nums[j]
                if total == k:
                    count += 1
        return count

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 11 LN

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();  // running-sum value -> occurrences
        seen.put(0, 1);
        int running = 0;
        int count = 0;
        for (int v : nums) {
            running += v;
            count += seen.getOrDefault(running - k, 0);
            seen.merge(running, 1, Integer::sum);
        }
        return count;
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 14 LN

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            int total = 0;
            for (int j = i; j < n; j++) {   // expand the stretch one element at a time
                total += nums[j];
                if (total == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED