算法之 前缀和

• 前缀和，就是定义pre[i] 为nums的前i个元素的和值，一般pre数组长度会=n+1,这样在计算的nums数组中下标i到j的情况的时候，直接就可以使用pre[j+1]-pre[i],如果找的是第i个到第j个，那么就是pre[j]-pre[i-1]
• 所以得根据题目求解的是下标还是第几个确定具体的计算公式
• 前缀和与哈希表：

前缀和基础

3427.变长子数组求和

3427.变长子数组求和

• 求解的是下标问题，所以是pre[j+1] - pre[i]类型

class Solution:
    def subarraySum(self, nums: List[int]) -> int:
        # 前缀和的问题
        n = len(nums)
        pre = [0]*(n+1)
        for i in range(n):
            pre[i+1] = pre[i] + nums[i]
        ans = 0
        for i in range(n):
            start = max(0,i-nums[i])
            ans += pre[i+1] - pre[start] 
        return ans

前缀和与哈希表

1524.和为奇数的子数组数目

1524.和为奇数的子数组数目

• 使用哈希表+前缀和，要注意这个前缀和的第一个也要加入哈希表！

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        # 直接用哈希表存储
        mod = 10**9 + 7
        store = [0,0]
        n = len(arr)
        # 使用前缀和
        pre = [0]*(n+1)
        for i in range(n):
            pre[i+1] = pre[i] + arr[i]
        ans = 0
        for i in range(n+1):
            if pre[i] % 2==0:
                ans = ans + store[1]
                store[0] = store[0] + 1
            else:
                ans = ans + store[0]
                store[1] = store[1] + 1
        return ans % mod

距离和