Given a slice of positive integers and a target, return the length of the
longest contiguous subarray that sums to exactly target. Return 0 if none
exists.
longestSubarraySum(nums, target)
Input format: nums | target.
[1, 1, 1, 1], target=2 // → 2
[3, 1, 1, 1, 2], target=3 // → 3 (1+1+1)
[5, 6], target=4 // → 0
A close cousin of finding any window that sums to the target, except now you need the longest one. Brute force — check every (start, end) pair, record the widest one summing to target — is O(n²), wasting effort re-summing overlapping ranges.
Since every number is positive, the same monotonic guarantee applies: extending on the right can only increase the sum, trimming from the left can only decrease it. A two-pointer variable window is safe — the effect of each move is always predictable.
Here's the subtlety separating "find one" from "find the longest." Earlier, once the sum equals target you stop. Here, a wider window found later might also match and beat your current best. So keep expanding, and every time the sum equals target, compare that window's width to the best seen so far.
The window only shrinks when its sum grows past the target. Positivity makes "sum too big" an unambiguous signal to trim from the left, one element at a time, until it's no longer over. You never shrink just because the sum is below target — that's fine, keep expanding.
right, adding each new element to a running sum.right - left + 1) and update the best if wider.right reaches the end; the best length is the answer, or 0 if none matched.Each element is added once and removed at most once, so both pointers only move forward — roughly 2n total movements instead of O(n²). The only change from "find any window" is tracking the best instead of stopping at the first hit.
def longest_subarray_sum(nums, target):
left = 0
total = 0
best = 0
for right in range(len(nums)):
total += nums[right]
while total > target and left <= right:
total -= nums[left]
left += 1
if total == target and right - left + 1 > best:
best = right - left + 1
return best
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.