Welcome to Subscribe On Youtube

3427. Sum of Variable Length Subarrays

Description

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.

 

Example 1:

Input: nums = [2,3,1]

Output: 11

Explanation:

i Subarray Sum
0 nums[0] = [2] 2
1 nums[0 ... 1] = [2, 3] 5
2 nums[1 ... 2] = [3, 1] 4
Total Sum   11

The total sum is 11. Hence, 11 is the output.

Example 2:

Input: nums = [3,1,1,2]

Output: 13

Explanation:

i Subarray Sum
0 nums[0] = [3] 3
1 nums[0 ... 1] = [3, 1] 4
2 nums[1 ... 2] = [1, 1] 2
3 nums[1 ... 3] = [1, 1, 2] 4
Total Sum   13

The total sum is 13. Hence, 13 is the output.

 

Constraints:

  • 1 <= n == nums.length <= 100
  • 1 <= nums[i] <= 1000

Solutions

Solution 1

  • class Solution {
    public int subarraySum(int[] nums) {
        int n = nums.length;
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + nums[i - 1];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += s[i + 1] - s[Math.max(0, i - nums[i])];
        }
        return ans;
    }
}


  • class Solution {
public:
    int subarraySum(vector<int>& nums) {
        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + nums[i - 1];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += s[i + 1] - s[max(0, i - nums[i])];
        }
        return ans;
    }
};


  • class Solution:
    def subarraySum(self, nums: List[int]) -> int:
        s = list(accumulate(nums, initial=0))
        return sum(s[i + 1] - s[max(0, i - x)] for i, x in enumerate(nums))


  • func subarraySum(nums []int) (ans int) {
	s := make([]int, len(nums)+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	for i, x := range nums {
		ans += s[i+1] - s[max(0, i-x)]
	}
	return
}


  • function subarraySum(nums: number[]): number {
    const n = nums.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + nums[i];
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        ans += s[i + 1] - s[Math.max(0, i - nums[i])];
    }
    return ans;
}

All Problems

All Solutions