Quick Overview

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.

Detect a Contiguous Subarray with a Target Sum

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## 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.

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

Given an integer array and an integer target, return whether at least one non-empty contiguous subarray has sum exactly equal to the target. The array may be empty and may contain positive, zero, and negative values, so the input must not be handled with a positive-only sliding window or mutated.

Constraints

  • 0 <= len(nums) <= 200000.
  • Every value in nums and target lies in [-10^9, 10^9].
  • The input may contain negative values.
  • The input array must not be mutated.
  • A matching subarray must be non-empty.
  • Prefix sums may exceed 32-bit range.

Examples

Input: ([3, -2, 5, -1], 4)

Expected Output: True

Explanation: This is the source example; the contiguous subarray [5, -1] sums to 4.

Input: ([], 0)

Expected Output: False

Explanation: An empty array has no non-empty subarray.

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.

Loading coding console...

Show the approach

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)