Given a slice of positive integers and a target, return the inclusive indices
[start, end] of a contiguous subarray that sums to exactly target. Return the
first such window (smallest end, then smallest start). If none exists, return an
empty slice.
findSubarraySum(nums, target)
Input format: nums | target. Output start end, or an empty line if none.
[1, 2, 3, 7, 5], target=12 // → [1, 3] (2+3+7 = 12)
[1, 2, 3, 4, 5], target=9 // → [1, 3] (2+3+4 = 9)
[1, 2, 3], target=100 // → []
Unlike the earlier problems, this window doesn't have a fixed width — you want any contiguous stretch, of any length, that sums to the target. Brute force checks every (start, end) pair, summing each from scratch: O(n²) pairs, with no fixed k to bound each window's cost.
A fast solution is possible because every number is positive. That guarantees: growing a window on the right can only increase its sum, and shrinking from the left can only decrease it. The sum moves monotonically depending on which side you touch. With negative numbers, this guarantee breaks, and you couldn't safely decide grow-or-shrink from the sum alone.
With two pointers, left and right:
right forward, adding each new element to a running sum.nums[left], advance left — until it's not.[left, right].right.Each element enters the window once (when right passes it) and leaves at most once (when left passes it). Neither pointer moves backward, so total movements are bounded by roughly 2n, not n² — no subarray gets re-examined once ruled out.
Checking every (start, end) pair directly is O(n²). Even a smarter brute force that maintains a running sum per fixed starting point still restarts for every new start — still O(n²) worst case. The two-pointer approach uses the monotonic sum property to decide, in O(1) amortized work per step, whether to grow or shrink — collapsing the search from quadratic to linear.
def find_subarray_sum(nums, target):
left = 0
total = 0
for right in range(len(nums)):
total += nums[right]
while total > target and left <= right:
total -= nums[left]
left += 1
if total == target:
return [left, right]
return None
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.