Length of the Longest Contiguous Subarray Summing to a Target

Given an integer array nums and an integer k, return the length of the longest contiguous subarray whose elements sum to exactly k. If no such subarray exists, return 0.

Function Signature

def longest_subarray_with_sum(nums: list[int], k: int) -> int:

Rules

• A subarray is a non-empty contiguous block nums[i..j] with i <= j.
• Elements may be negative, zero or positive.
• Only the length is returned, so it does not matter which of several longest qualifying subarrays you have in mind.

Constraints

• 1 <= len(nums) <= 2 * 10^5
• -10^4 <= nums[i] <= 10^4
• -10^9 <= k <= 10^9
• Every subarray sum lies within [-2 * 10^9, 2 * 10^9], which fits in a 32-bit signed integer.

Examples

Example 1

Input:  nums = [2, -1, 3, 1, -2, 2], k = 3
Output: 5

Both [2, -1, 3, 1, -2] and [-1, 3, 1, -2, 2] sum to 3. The whole array sums to 5, so no subarray of length 6 qualifies.

Example 2

Input:  nums = [1, 2, 3], k = 7
Output: 0

The largest possible sum is 6, so no subarray sums to 7.

Example 3

Input:  nums = [0, 0, 0], k = 0
Output: 3

The whole array sums to 0.

Longest Contiguous Subarray with an Exact Target Sum

Given an integer array nums and an integer k, return the length of the longest contiguous subarray whose elements sum to exactly k. If no such subarray exists, return 0.

Implement longest_subarray_with_sum(nums, k).

Rules

• A subarray is a non-empty contiguous block nums[i..j] with i <= j.
• Elements may be negative, zero or positive.
• Only the length is returned, so it does not matter which of several longest qualifying subarrays you have in mind.

Constraints

• 1 <= len(nums) <= 2 * 10^5
• -10^4 <= nums[i] <= 10^4
• -10^9 <= k <= 10^9
• Every subarray sum lies within [-2 * 10^9, 2 * 10^9], which fits in a 32-bit signed integer.

The elements, k, every subarray sum and the returned length all fit in a 32-bit signed integer, so the Java and C++ signatures use int. A value obtained by subtracting k from such a sum can reach 3 * 10^9 in magnitude, which exceeds 2^31 - 1; if your approach computes one, use 64-bit integers for it (long in Java, long long in C++).

Example 1

Input:  nums = [2, -1, 3, 1, -2, 2], k = 3
Output: 5

Both [2, -1, 3, 1, -2] and [-1, 3, 1, -2, 2] sum to 3. The whole array sums to 5, so no subarray of length 6 qualifies.

Example 2

Input:  nums = [1, 2, 3], k = 7
Output: 0

The largest possible sum is 6, so no subarray sums to 7.

Hints

1. Elements may be negative or zero, so a block's sum can fall as the block grows; do not assume that lengthening a block only increases its sum.
2. Only the length is returned: when several different blocks share the maximum length the answer is that length, and when no block sums to k the answer is 0.
3. A qualifying block may start at index 0, end at the last index, or cover the whole array; make sure your approach does not miss any of these positions.

Approach

Algorithm: scan nums once while maintaining the running prefix sum P (the sum of nums[0..i]) and a hash map from each prefix-sum value to the FIRST index at which it occurred. The map is seeded with value 0 at index -1, which represents the empty prefix. At index i, after adding nums[i] to P, look up P - k: if it was first seen at index s, then nums[s+1..i] sums to exactly k and has length i - s, so update the best length. Only after the lookup, record P at index i if P has never been seen; an existing entry is never overwritten.

Invariant: before processing index i, the map holds, for every value v among the prefix sums of lengths 0..i, the smallest prefix position (shifted by -1) whose sum is v.

Correctness: the subarray nums[s+1..i] sums to k exactly when prefix(i) - prefix(s) = k, i.e. prefix(s) = P - k. For a fixed right end i, the longest such subarray uses the smallest s, which is exactly what the first-occurrence map returns; taking the maximum over all right ends therefore gives the longest qualifying subarray overall, and 0 when no lookup ever succeeds. Looking up before inserting guarantees s < i, so every counted subarray is non-empty. Because only lengths are compared, which of several equally long subarrays is found does not matter.

Why simpler ideas fail: elements can be negative, so a window's sum is not monotonic in its length and a grow/shrink sliding window can discard the correct start (for example [5, -3, 1] with k = 3). Overwriting a prefix value with a later index shortens answers (for example [1, -1, 1, -1, 1] with k = 1), and forgetting the empty prefix misses every subarray that starts at index 0.

Edge cases: a single element (answer 1 or 0), no qualifying subarray (0), k = 0 with runs of zeros, qualifying subarrays at the start, end, middle or covering the whole array, and k at the +/-10^9 bounds. Every subarray sum fits in 32 bits, but P - k can reach 3 * 10^9 in magnitude, so Java and C++ keep P and the lookup key in 64-bit integers.

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