Easy

题目描述

给定一个大小为 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

示例 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

约束条件：

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

解题思路

这道题要求我们计算所有可变长度子数组的元素总和。对于每个位置 i，子数组的起始位置由 start = max(0, i - nums[i]) 决定。

解法一：暴力求解（推荐） 由于题目约束条件较小（n ≤ 100），我们可以直接使用暴力方法：

  1. 遍历每个位置 i
  2. 计算对应子数组的起始位置 start = max(0, i - nums[i])
  3. 累加子数组 nums[start…i] 的所有元素
  4. 将所有子数组的和相加得到最终结果

解法二：前缀和优化 虽然暴力解法已经足够，我们也可以使用前缀和来优化子数组求和的过程，将每次子数组求和从 O(n) 降到 O(1)。

两种解法的时间复杂度都是 O(n²)，但前缀和解法在实际运行中会稍快一些。考虑到题目约束较小且代码简洁性，推荐使用暴力解法。

代码实现

class Solution {
public:
    int subarraySum(vector<int>& nums) {
        int n = nums.size();
        int totalSum = 0;
        
        for (int i = 0; i < n; i++) {
            int start = max(0, i - nums[i]);
            int currentSum = 0;
            for (int j = start; j <= i; j++) {
                currentSum += nums[j];
            }
            totalSum += currentSum;
        }
        
        return totalSum;
    }
};

class Solution:
    def subarraySum(self, nums: List[int]) -> int:
        n = len(nums)
        total_sum = 0
        
        for i in range(n):
            start = max(0, i - nums[i])
            current_sum = sum(nums[start:i+1])
            total_sum += current_sum
        
        return total_sum

public class Solution {
    public int SubarraySum(int[] nums) {
        int n = nums.Length;
        int totalSum = 0;
        
        for (int i = 0; i < n; i++) {
            int start = Math.Max(0, i - nums[i]);
            int currentSum = 0;
            for (int j = start; j <= i; j++) {
                currentSum += nums[j];
            }
            totalSum += currentSum;
        }
        
        return totalSum;
    }
}

var subarraySum = function(nums) {
    const n = nums.length;
    let totalSum = 0;
    
    for (let i = 0; i < n; i++) {
        const start = Math.max(0, i - nums[i]);
        let currentSum = 0;
        for (let j = start; j <= i; j++) {
            currentSum += nums[j];
        }
        totalSum += currentSum;
    }
    
    return totalSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)外层循环 O(n)，内层求和最坏情况 O(n)
空间复杂度O(1)只使用常数额外空间

相关题目