跳转至

3427. 变长子数组求和

题目描述

给你一个长度为 n 的整数数组 nums 。对于 每个 下标 i（0 <= i < n），定义对应的子数组 nums[start ... i]（start = max(0, i - nums[i])）。

返回为数组中每个下标定义的子数组中所有元素的总和。

子数组 是数组中的一个连续、非空 的元素序列。

 

示例 1：

输入：nums = [2,3,1]

输出：11

解释：

下标 i 子数组 和
0 nums[0] = [2] 2
1 nums[0 ... 1] = [2, 3] 5
2 nums[1 ... 2] = [3, 1] 4
总和   11

总和为 11 。因此，输出 11 。

示例 2：

输入：nums = [3,1,1,2]

输出：13

解释：

下标 i 子数组 和
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
总和   13

总和为 13 。因此，输出为 13 。

 

提示：

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

解法

方法一

1
2
3
4
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))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
}

评论