Problem overview
The function subarray_sum receives a vector of non-negative integers, nums, and a target. It must return the start and end indices, as a vector [start, end], of a continuous subarray whose elements add up to target. Both indices are inclusive. When no subarray matches, the function returns [-1, -1]. If several subarrays match, any of them is accepted.
In the example, nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and target = 21. The elements at indices 2 to 6 are 5, 2, 1, 3 and 10, which add up to 21, so the answer is [2, 6].
The statement asks for O(n) time and O(1) extra space, so the code can't build a table of prefix sums.
Approach: a window whose sum never has to be recomputed
The brute-force way tries every start and every end and adds up each subarray. That is O(n^3), or O(n^2) with a running sum per start.
The key fact is that all numbers are non-negative. Adding an element to a subarray never lowers its sum, and removing one never raises it. That gives a simple rule for a window [j, i] with running sum sum:
- if
sumis too small, extend the window on the right; - if
sumis too big, shrink it on the left; - if
sumequalstarget, return the window.
Shrinking from the left is safe because a bigger sum can only be fixed by dropping elements. The right end i comes from the for loop and moves one step each time. The left end j only moves forward. Neither index goes back, so there are at most about 2n moves in total.
On the example, the running sum grows 1, 2, 7, 9, 10, 13 and reaches 23 when the 10 at index 6 joins. That is above 21, so the window drops index 0 (sum 22) and then index 1 (sum 21), and stops, because the sum is no longer above the target. The window is now [2, 6] and its sum equals the target.
Step by step
- Declare the window's left end and the sum as two mutable variables:
j, ausizebecause it indexesnums, andsum, ani32like the numbers it adds up. Both start at 0. - Loop over every right end
iin0..nums.len(). Each iteration makesnums[i]the last element of the window. - Add
nums[i]tosum, since it joins the window. - Shrink while the sum is too big. A
whileloop runs whilej < iandsum > target. The conditionj < ikeepsnums[i]in the window: even if it is larger than the target alone, the window never becomes empty. - Drop the leftmost element. Subtract
nums[j]fromsum. - Move
jforward withj += 1. Rust has no++. - Check for a match. After the
whileloop, ifsum == target, returnvec![j as i32, i as i32]. Both indices areusize, and the function returnsVec<i32>, so they are cast. The first match found is the one that ends earliest. - Return
vec![-1, -1]after the loop, as the final expression, with noreturnand no semicolon.
The solution in Rust
impl Solution {
fn subarray_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut j: usize = 0;
let mut sum: i32 = 0;
for i in 0..nums.len() {
sum += nums[i];
while j < i && sum > target {
sum -= nums[j];
j += 1;
}
if sum == target {
return vec![j as i32, i as i32];
}
}
vec![-1, -1]
}
}
The Rust details worth a closer look:
- Two kinds of return. The early
return vec![...];leaves the function from inside the loops. The last line,vec![-1, -1], has no semicolon, so it is the value of the function when the loop ends without a match. - The
ascasts.j as i32converts ausizeto ani32. Casts withasnever panic and silently truncate if the value doesn't fit. For indices of a vector that fits in memory and an answer of this size, that is fine here. - Why
j < iguards the subtraction. Without it,jcould passiand the window would be empty or backwards. Becausejstays belowiandiis a valid index,nums[j]is always valid too. - Integer overflow. The sum is an
i32. The lessons build with optimizations, where overflow wraps silently:2_000_000_000 + 2_000_000_000gives-294967296. In a debug build the same addition panics. The lesson's tests keep the sums small. For large inputs, use ani64forsum.
Complexity
Time: O(n). i goes through the vector once. j only increases and never passes i, so the inner while loop runs at most n times over the whole call. Each step is constant work.
Space: O(1). The function keeps two indices and a sum, however long the vector is. The returned two-element vector is the answer and doesn't depend on the input size.
Edge cases and common mistakes
- No match.
[1, 2, 3]with target 7 returns[-1, -1]. - Empty vector. The loop doesn't run, so the result is
[-1, -1], even with a target of 0. - A single element.
[4]with target 4 returns[0, 0]. The subarray may have length 1. - A big element. In
[7, 3]with target 3, the 7 alone exceeds the target, but the window may not be empty at that point. The next iteration adds the 3, drops the 7 and returns[1, 1]. - Zeros.
[5, 0]with target 0 returns[1, 1]: the 5 is dropped, and the lone 0 is a valid subarray. Zeros are the reason the rule is "non-negative" and not "positive". Because the check issum > targetand not>=, a window with equal sum stays and is returned. - Several answers.
[0, 0, 4]with target 4 returns[0, 2].[2, 2]would also be valid, and any of them is accepted. - Negative numbers. The method only works because every number is non-negative. With negatives, a sum that is too big could become right again by adding more elements, and this scan would miss answers.
Testing
nums = [1, 1, 5, 2, 1, 3, 10, 2, 1],target = 21gives[2, 6].nums = [1, 2, 3, 4],target = 5gives[1, 2].nums = [1, 2, 3],target = 6gives[0, 2].nums = [7, 3],target = 3gives[1, 1].nums = [3],target = 0gives[-1, -1].nums = [],target = 0gives[-1, -1].
