Subarray Sum Equals K
Medium About 20 min Free, no account needed
Count contiguous subarrays whose elements sum to a target k.
The brief
Given an integer array nums and an integer k, return the number of contiguous
subarrays whose elements sum to exactly k. Values may be negative.
The obvious approach sums every subarray, O(n²). The hidden test uses 200,000
elements, so the quadratic version is too slow. Aim for CountSubarrays in
O(n).
The count can exceed
int.MaxValue, so the method returns along.
Starter code
using System;
public class Solution
{
// TODO: return the number of contiguous subarrays whose sum equals k.
public long CountSubarrays(int[] nums, int k)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Prefix sums
- Carry running totals or prefix state so any range question becomes a lookup.
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Longest Well-Performing Interval Hard Free Longest stretch of days with more tiring days than easy ones.
- Degree of an Array Medium Free Find the shortest contiguous slice whose most-frequent-element count matches the whole array.
- Find All Anagram Start Indices Medium Free Every position where an anagram of the pattern begins.