Problem overview
The function subarraySum receives a slice nums of non-negative integers and a number target. It must find a contiguous subarray whose elements add up to exactly target and return its first and last indices as a two-element []int. If no subarray works it returns []int{-1, -1}. When several subarrays qualify, any of them is accepted.
In the example, nums = []int{1, 1, 5, 2, 1, 3, 10, 2, 1} and target = 21. The elements at indices 2 to 6 are 5, 2, 1, 3, 10, which add up to 21, so the answer is [2, 6].
The statement asks for O(n) time and O(1) extra space.
Approach: grow on the right, shrink on the left
The brute force tries every start and every end and sums the elements between them, which is O(n²) pairs at least. The linear solution rests on the fact that all numbers are non-negative:
- adding an element on the right never decreases the sum;
- removing an element on the left never increases it.
So the sum of a window moves in a predictable direction, and you can always tell which end to move. Keep the window as nums[j..i] with its sum in sum:
- Move
iforward one position at a time. The new element joins the window. - While the sum is greater than
target, drop elements from the left by movingjforward. A sum that is too large can only be repaired by removing elements, and the only elements that can go without breaking contiguity are the leftmost ones. - After that, either the sum equals
target, and the window is an answer, or it is smaller thantarget, soimust move on to bring in more.
Neither index ever moves backwards, so each element joins the window once and leaves at most once.
The loop is guarded by j < i. This keeps at least one element in the window, namely nums[i]. If a single element is already larger than target, the window shrinks to just that element and cannot match. On the next iteration nums[i + 1] joins, and the shrinking continues from there.
On the example:
- For
ifrom 0 to 5 the sum grows: 1, 2, 7, 9, 10, 13. It never exceeds 21, sojstays at 0. - At
i = 6the new element 10 makes the sum 23. Droppingnums[0]andnums[1](two 1s) brings it to 21, andjis now 2. - The sum equals the target, so the function returns
[2, 6].
Step by step
- Declare
jandsumin one:=statement, both 0.jis the left end of the window andsumis its total. - Loop over
ifrom 0 tolen(nums) - 1. Each pass makesnums[i]the right end of the window. - Add
nums[i]tosum. - Shrink while the sum is too big with a condition-only
for:j < iandsum > target. Go has nowhile, and aforwith just a condition does the same job. - Subtract
nums[j]fromsum, because that element leaves the window. - Move
jforward by one. - Check for a match. After the shrinking loop, if
sum == target, return[]int{j, i}. Returning right away gives the subarray that ends earliest. - Return
[]int{-1, -1}after the loop, because no window matched.
The solution in Go
func subarraySum(nums []int, target int) []int {
j, sum := 0, 0
for i := 0; i < len(nums); i++ {
sum += nums[i]
for j < i && sum > target {
sum -= nums[j]
j++
}
if sum == target {
return []int{j, i}
}
}
return []int{-1, -1}
}
The Go details worth knowing:
- Several variables in one
:=.j, sum := 0, 0declares twointvariables. Go would reject the program if either were never used. - Condition-only
for.for j < i && sum > targethas no init or post statement. It is how Go spells a while loop. - Returning a slice literal.
[]int{j, i}builds a new two-element slice. Go functions can return values directly from an expression, so no temporary variable is needed. intis 64 bits here, so sums of ordinary test values never overflow. If they could exceed the 64-bit range,sumwould wrap around silently instead of raising an error.
Complexity
Time: O(n). The outer loop runs n times. j only moves forward and never passes i, so over the whole run the inner loop executes at most n times in total.
Space: O(1). The function keeps two indices and a running sum, plus the two-element result.
Edge cases and common mistakes
- Empty slice. The loop never runs and the result is
[-1, -1]. This holds even whentargetis 0, because the function never returns an empty subarray. - No match.
nums = []int{1, 2, 3}andtarget = 100returns[-1, -1]. - A single element.
nums = []int{7}andtarget = 7returns[0, 0]. - A target of 0.
nums = []int{0}returns[0, 0], andnums = []int{1, 2}returns[-1, -1], because the only way to reach 0 is with zero elements, which isn't a subarray. - Zeros in the slice.
nums = []int{3, 0, 0, 3}andtarget = 3returns[0, 0]. Other answers such as[0, 2]and[3, 3]are also valid, and the statement accepts any of them. - A large element in front.
nums = []int{8, 1, 2}andtarget = 3returns[1, 2]: the 8 is dropped from the window as soon as the next element arrives. - Dropping the
j < iguard. The shrinking loop could then removenums[i]itself and leave an empty window with sum 0. Withnums = []int{1, 2}andtarget = 0, the function would return the invalid pair[1, 0]instead of[-1, -1]. - Negative numbers. The method needs non-negative values. With negatives, a window that is too big could become right by adding more, and one that is too small could become right by dropping an element. A map of prefix sums solves that variant.
Testing
nums = []int{1, 1, 5, 2, 1, 3, 10, 2, 1},target = 21gives[2 6].nums = []int{1, 2, 3},target = 100gives[-1 -1].nums = []int{7},target = 7gives[0 0].nums = []int{8, 1, 2},target = 3gives[1 2].nums = []int{},target = 0gives[-1 -1].