Detect a Contiguous Subarray with a Target Sum

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.

Hint: 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.

Edge Cases

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

Detect a Contiguous Subarray with a Target Sum

Hints

1. Express a subarray sum as the difference between two prefix sums.
2. Before adding the current prefix to a set, ask whether current_prefix - target has already appeared.

Approach

Let the prefix sum before the array be zero. At each element, update the current prefix sum. A non-empty subarray ending at this element has sum target exactly when an earlier prefix sum equals current prefix minus target. Store every prefix sum seen strictly before the next check in a set, beginning with zero. Finding the required difference therefore proves a matching subarray exists. Conversely, every non-empty contiguous subarray is the difference of its ending prefix and an earlier prefix, so any matching subarray will trigger the check at its end. Prefix sums use wide integer types because they can exceed 32-bit range.

• Time complexity: O(n)
• Space complexity: O(n)