题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给了一个整型数组，对其中的每一个元素，都要根据一个要求创建一个子数组，而题目要求则要返回这些所有子数组的数值和。

思路分享

  • 前缀和的思路，可以参考 【Leetcode Daily】303区域和检索-数组不可变

  • 由于题目子数组和求得的方式，可以通过前缀和方便完成，所以采用这种方法。

  • 重要的是，终于搞清楚了 Python 中 accumulate 函数到底是怎么形成的。对于 [1, 2, 3] 这样的列表，accumulate([1, 2, 3]) 会产生 [1, 3, 6]，也就是前缀和，但是通过增加参数 initial 的值可以改变初始前缀和值（该参数默认为 None），比如 accumulate([1, 2, 3], initial=0)，会在初始的地方增加一个 0，变成 [0, 1, 3, 6]；accumulate([1, 2, 3], initial=1)，就是 [1, 2, 4, 7]。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
class Solution:
    def subarraySum(self, nums: List[int]) -> int:
        pre = list(accumulate(nums, initial=None))
        # pre = list(accumulate(nums, initial=0))
        ans = 0
        pre.insert(0, 0) # 补充没有的 0
        for i, x in enumerate(nums):
            ans += pre[i+1] - pre[max(0, i-nums[i])] 
        return ans