Return true if some non-empty contiguous subarray sums to exactly target. The
array may contain negative numbers, so a sliding window won't work — use prefix sums
and a hash set.
hasSubarraySum(nums, target)
Input format: nums | target.
[1, 2, 3], target=5 // → true (2+3)
[1, 2, 3], target=7 // → false
[3, -1, -1, 4], target=2 // → true (-1-1+4)
The literal approach checks every contiguous subarray: for each start, extend forward tracking the sum. O(n²) in the worst case.
Sliding windows rely on growing the window only increasing the sum, and shrinking only decreasing it — which requires non-negative values. Negative numbers break that: growing the window could move the sum either direction, so you can't safely decide whether to grow or shrink. A sliding window gives wrong answers here, not just slow ones.
Think of a subarray as the difference of two prefix sums: the sum from just after index i through j equals (prefix through j) minus (prefix through i). So "does some subarray sum to target?" becomes "do two prefix sums exist whose difference is target?"
As you compute the running prefix sum left to right, ask at each position: have I already seen a prefix sum equal to (current sum − target)? If yes, the subarray between that position and here sums to target. You only need membership, not positions — a hash set, O(1) average lookup.
Seed the set with 0 before starting: that's the empty prefix, letting a subarray starting at the very beginning be detected correctly.
Unlike the sliding window, this makes no assumption about monotonicity — it's just asking whether a specific earlier prefix sum occurred, valid regardless of sign. Prefix sums plus a hash set are the standard technique whenever negatives are allowed: O(n²) exhaustive check collapses to a single O(n) pass.
def has_subarray_sum(nums, target):
seen = {0}
total = 0
for n in nums:
total += n
if total - target in seen:
return True
seen.add(total)
return False
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.