前缀和

谨记： 数组不是单调的话，不要用滑动窗口，考虑用前缀和 用来解决的问题：计算连续子数组的和

• 303-区域和检索
• 560-和为k的子数组

算法思想

• 原数组 a=[-2,0,3,-5,2,-1]
• 前缀和数组 s=[0,-2,-2,1,-4,-1,-3]

定义s=[0]*(len(a)+1)
s[0]=0
s[1]=a[0]
s[2]=a[0]+a[1]
.
.
.
s[n+1]=a[0]+a[1]+...+a[n]

要计算a中left指针到right指针的和:
r=right指针 l=left指针
前缀和数组s：
s[r+1]=a[0]+a[1]+...+a[r]
s[l]=a[0]+...+a[l-1]
=> s[r+1]-s[l]=a[l]+...+a[r]

s=[0]*(len(nums)+1)
for i in range(len(nums)):
	s[i+1]=s[i]+nums[i]

Q:为什么要定义s[0]=0? A: 如果不定义s[0]=0 那么就要算s[r]=s[l-1]，如果l=0就需要分情况讨论了（s[-1]会有error）