Subarray Sum Equals K

Isomorphic Strings

Single Number II

Count how many contiguous subarrays add up to exactly the target value k.

Given an integer array `nums` and an integer `k`, return the total number of contiguous subarrays whose elements sum to exactly `k`.

**Input / output**
- Input: `nums: int[]`, `k: int`
- Output: the count of qualifying subarrays

**Examples**
1. `nums = [1, 1, 1]`, `k = 2` returns `2`.
2. `nums = [1, 2, 3]`, `k = 3` returns `2`.
3. `nums = [1, -1, 0]`, `k = 0` returns `3`.

**Constraints**
- `1 <= nums.length <= 20000`
- `-1000 <= nums[i] <= 1000`
- `-10^7 <= k <= 10^7`

**Edge cases**
- Values may be negative or zero, so sliding-window shrinking does not apply.
- Subarrays that start at index `0` are counted via an initial prefix sum of `0`.

**Target complexity**
- Aim for `O(n)` time and `O(n)` extra space.

**Hints**
1. A subarray sum equals `prefix[j] - prefix[i]`; you want that difference to equal `k`.
2. While scanning, count how many earlier prefix sums equal `current - k`.

**Follow-up**
Why does the negative-number case rule out the classic shrinking sliding-window approach?

- Let `prefix[i]` be the sum of the first `i` elements.
- The sum of the subarray `(i, j]` is `prefix[j] - prefix[i]`.
- We want pairs where that difference equals `k`.

Reframe as prefix sums

- Try every start index and extend a running sum to every end index.
- Count whenever the running sum hits `k`. This is `O(n^2)`.

Brute-force every subarray

- Walk once, keeping the running prefix sum.
- For each prefix, the number of valid subarrays ending here equals how many earlier prefixes equalled `prefix - k`.
- Seed the map with `{0: 1}` so subarrays starting at index `0` are counted.

Count complementary prefixes

- Store how many times each prefix sum has occurred.
- Add `counts[prefix - k]` to the answer before recording the current prefix.

One-pass hashmap solution

Trace `nums = [1, 1, 1]`, `k = 2`, starting with `counts = {0: 1}`.

| num | prefix | prefix - k | added | counts |
|---:|---:|---:|---:|---|
| 1 | 1 | -1 | 0 | `{0:1, 1:1}` |
| 1 | 2 | 0 | 1 | `{0:1, 1:1, 2:1}` |
| 1 | 3 | 1 | 1 | `{0:1, 1:1, 2:1, 3:1}` |

Total `= 2`.

Dry run

The prefix-sum hashmap counts every qualifying subarray in `O(n)` time and `O(n)` extra space.