Indexes of Subarray Sum

Indexes of Subarray Sum is a classic sliding window problem. When an array has only non-negative numbers, you can find a contiguous run that adds up to a target by growing and shrinking a single window — no nested loops needed.

The slow way first

The obvious idea: try every starting index, then extend a second loop forward adding numbers until you hit or pass the target. That works, but it is O(n²) — for each of the n starts you may scan most of the array again.

The question to ask: do I really need to recompute each window from scratch? No. When I move the right edge one step right, the new sum is just the old sum plus one number. And when the sum gets too big, I can drop numbers off the left edge instead of starting over. That reuse is what makes one pass enough.

The idea: one window, two edges

Keep a window bounded by start and end, and a running total of everything inside it. Walk end across the array. At each step:

• Expand: add nums[end] to total.
• Shrink: while total is greater than the target, subtract nums[start] and move start right.
• Check: if total now equals the target, the window is the answer.

Because every number is positive, growing the window can only increase the sum and shrinking can only decrease it — so this monotonic behavior is exactly what lets a single window find the answer.

The key insight: start only ever moves forward, and so does end. Each pointer travels the array at most once, so the total work is linear even though there are two loops in the code.

Walk through it

Step through the animation. end slides right adding 1, 2, 3 — the running total climbs to 6, still short of 12. Adding 7 pushes total to 13, which overshoots, so the window shrinks: we drop the leftmost 1, leaving total = 12 and start at the value 2. Now total == target, so the window [2, 3, 7] is the answer and we return its 1-based bounds [2, 4].

Pseudocode

start = 0
total = 0
for end from 0 to n-1:
    total += nums[end]            # expand the window to the right
    while total > target:         # window sum too big
        total -= nums[start]      # drop the leftmost number
        start += 1
    if total == target:           # exact match
        return [start + 1, end + 1]   # convert to 1-based
return [-1]                       # no subarray found

The Python solution

def subarray_sum(nums, target):
    start = 0
    total = 0
    for end in range(len(nums)):
        total += nums[end]
        while total > target:
            total -= nums[start]
            start += 1
        if total == target:
            return [start + 1, end + 1]
    return [-1]

• start is the left edge of the window; total is the sum of everything currently inside it.
• The for loop drives the right edge: each iteration adds nums[end] to the window.
• The while loop is the shrink phase — as long as the sum exceeds the target, peel numbers off the left.
• Line 9 checks for an exact hit; line 10 returns the bounds, adding 1 to each index to make them 1-based.
• If the loop finishes without a match, we return [-1].

Complexity

Even though there is a while loop inside the for loop, start advances at most n times across the whole run, so the combined work is O(n). We use only a couple of variables, so the extra space is O(1).

When this pattern shows up

Practice