Katkat
Back

Detect a Contiguous Subarray with a Target Sum

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Determine whether an integer array containing negative values has any nonempty contiguous subarray that equals a target, using prefix sums for a linear-time solution.

Problem

Given an integer array and a target, return whether at least one non-empty contiguous subarray has sum exactly equal to the target.

Function Contract

Implement has_target_sum_subarray(nums, target) -> bool.

Constraints

  • 0 <= len(nums) <= 200000.
  • Values and target lie in [-10^9, 10^9].
  • The input may contain negative values, so a positive-only sliding window is insufficient.
  • The input array must not be mutated.

Examples

  • nums = [3,-2,5,-1], target 4 returns true for subarray [5,-1].
  • nums = [], target 0 returns false because the subarray must be non-empty.

Edge Cases

  • A single element can be the answer.
  • The target can be zero.
  • Prefix sums may exceed 32-bit range.

Hints

Hint 1

Compare prefix sums: A subarray ending at the current index sums to the target when an earlier prefix sum equals the current prefix minus the target.