Sum of variable length subarrays

Array Prefix Sum

85.5% acceptance

Feb 25, 2026

108

You are given an integer array nums of size n. For each index i where 0 <= i < n, define a subarray nums[start ... i] where start = max(0, i - nums[i]). Return the total sum of all elements from the subarray defined for each index in the array.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn subarray_sum(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut prefix = vec![0i32; n + 1];
    for i in 0..n { prefix[i + 1] = prefix[i] + nums[i]; }
    let mut ans = 0i32;
    for i in 0..n {
      let start = i.saturating_sub(nums[i] as usize);
      ans += prefix[i + 1] - prefix[start];
    }
    ans
  }
}