Count subarrays summing to target
Company: TikTok
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
LeetCode 560. Subarray Sum Equals K – Given an integer array nums and an integer k, return the total number of continuous subarrays whose sum equals k. Variants:
(a) return a boolean indicating whether any such subarray exists,
(b) if all numbers are positive, achieve O(
1) extra space using the sliding-window technique.
https://leetcode.com/problems/subarray-sum-equals-k/description/
Quick Answer: This question evaluates a candidate's understanding of array algorithms, cumulative-sum reasoning, and time/space complexity considerations when identifying subarrays with a target sum. Commonly asked in the Coding & Algorithms domain to probe algorithmic problem-solving, data-structure reasoning, and optimization skills, it targets practical application rather than purely conceptual theory.
Given an integer array nums and an integer k, return the number of non-empty contiguous subarrays whose sum equals k. nums may contain negative numbers and zeros. Return the count as an integer.
Constraints
- 0 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- -10^9 <= k <= 10^9
- Subarrays are contiguous and non-empty
- Result may exceed 32-bit integer range
Hints
- Use a running prefix sum and a hash map storing frequencies of prefix sums seen so far.
- If current prefix is s, then the number of subarrays ending here with sum k equals the frequency of (s - k).
- Initialize the map with {0: 1} to count subarrays that start at index 0.
- If all numbers are positive, a sliding window achieves O(1) extra space, but it does not work with negative numbers.