Count subarrays summing to target
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an integer array nums and an integer target T, return the number of contiguous subarrays whose sum equals T. Provide an algorithm that runs in linear time using appropriate data structures, and explain how it handles negative numbers and edge cases (e.g., T = 0, empty prefix). Analyze time and space complexity.
Quick Answer: This question evaluates understanding of prefix-sum concepts, use of linear-time data structures, and competence in handling negative numbers and edge cases such as zero targets and empty prefixes.
Given an integer array `nums` and an integer `target`, return the total number of contiguous subarrays whose elements sum exactly to `target`.
A subarray is a contiguous (non-empty) slice of the array. Two subarrays that occupy different index ranges count separately even if they contain the same values.
The array may contain negative numbers, zeros, and duplicates, so a sliding-window approach does not work. Aim for an O(n) time solution.
**Example 1:**
```
Input: nums = [1, 1, 1], target = 2
Output: 2
Explanation: The subarrays [1,1] (indices 0..1) and [1,1] (indices 1..2) each sum to 2.
```
**Example 2:**
```
Input: nums = [1, 2, 3], target = 3
Output: 2
Explanation: [1,2] and [3] both sum to 3.
```
**Example 3:**
```
Input: nums = [0, 0, 0], target = 0
Output: 6
Explanation: Every one of the C(3+1, 2) = 6 contiguous ranges sums to 0.
```
Constraints
- 1 <= nums.length <= 2 * 10^4 (an empty array trivially returns 0)
- -1000 <= nums[i] <= 1000
- -10^7 <= target <= 10^7
- The array may contain negatives, zeros, and duplicate values.
Examples
Input: ([1, 1, 1], 2)
Expected Output: 2
Explanation: Subarrays [1,1] at indices 0..1 and [1,1] at indices 1..2 each sum to 2.
Input: ([1, 2, 3], 3)
Expected Output: 2
Explanation: [1,2] and [3] both sum to 3.
Hints
- Define prefix[i] = nums[0] + ... + nums[i-1]. A subarray (l, r) sums to target exactly when prefix[r+1] - prefix[l] == target.
- Rearrange: for each running prefix sum S, you need the count of earlier prefix sums equal to S - target. Maintain a hash map from prefix-sum value to how many times it has occurred so far.
- Seed the map with {0: 1} before the loop. That entry represents the empty prefix and is what lets a subarray starting at index 0 be counted (it handles target sums that begin at the very front, including target = 0).
- Because you only ever look at prefix sums seen *before* the current index, the method works correctly with negative numbers and zeros where sliding windows fail.