（Python）前缀和

前缀和：

• 前缀和预先计算并存储一系列连续元素的总和，是一种优化技巧，提高算法效率。
• 记录一个数组中各下标位置之前的所有元素的总和，本文对应下标的总和中不含对应下标元素本身。若有需要也可以对应下标记录的总和包含下标本身元素，只需注意下标正确即可。
• 一维前缀和数组S，第一个元素为0，即S[0]=0，其他元素为S[i] = S[i-1] + 数组[i-1]，即S[i] = 数组[0] + 数组[1] + ... + 数组[i-1]。
• 例如：数组[1,3,5]，前缀和数组为[0,1,4,9]。
• 因本文中下标对应前缀和不包含下标本身元素，则子数组和即原数组左侧下标l（含）到右侧下标r（含）之间的和：前缀和列表中S[r+1] - S[l]，子数组长度为r+1-l。
• 若记录一个数组中各下标位置之前的所有元素的乘积，第一个元素为1，因若第一个元素为0则乘积结果都为0。
• 例如：数组[1,3,5]，前缀积数组为[1,1,3,15]。
• 注：本文前缀和数组比原数组长度多1。
• 补充：后缀和（记录一个数组中各下标位置之后的所有元素的总和）。
• 补充：二维前缀和S，第一行第一列均为0，其他 S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + 数组[i-1][j-1] （i为行下标，j为列下标）。

---

案例：【力扣】

1、（难度：简单）

【Python3】

解题思路：依次遍历数组中元素，分别计算左侧所有元素总和（前缀和，不含当前元素）与右侧所有元素总和（后缀和，不含当前元素），判断前缀和与后缀和是否相同，相同则下标为中心下标，返回下标。遍历完，没有中心下标，返回-1。

class Solution:def pivotIndex(self, nums: List[int]) -> int:# 数组长度n = len(nums)# 数组中所有元素总和total = sum(nums)# 左侧所有元素总和，初始为0sum_left = 0# 遍历数组，判断左侧和与右侧和是否相同for i in range(n):# 右侧所有元素总和（后缀和，不含当前元素）sum_right = total - sum_left - nums[i]# 若左侧和与右侧和相同，则为中心下标if sum_left == sum_right: return i# 当前元素加入左侧和（前缀和，不含当前元素），为下一个元素进行判断sum_left += nums[i]# 不存在中心下标return -1

2、（难度：中等）

【Python3】

解题思路：三个数组分别记录所在下标左侧所有元素的乘积、所在下标右侧所有元素的乘积、除了下标以外其他所有元素的乘积（左侧与右侧的乘积）。

先从头到尾遍历元素，记录左侧所有元素的乘积。再从后往前遍历元素，记录右侧所有元素的乘积。最后记录左侧和右侧的乘积。

注：乘积初始为1，若初始为0乘积结果都为0。

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:n = len(nums)res_prev, res_suffix= [1] * n, [1] * n# 下标i（不含）左侧所有元素的乘积for i in range(1, n):res_prev[i] = res_prev[i - 1] * nums[i - 1]# 下标i（不含）右侧所有元素的乘积for i in range(n - 2, -1, -1):res_suffix[i] = res_suffix[i + 1] * nums[i + 1]# 记录除了下标i其他所有元素的乘积（左侧与右侧的乘积）answer = [0] * nfor k in range(n):answer[k] = res_prev[k] * res_suffix[k]return answer

也可用一个数组和一个常数，数组先记录左侧所有元素的乘积，再记录左侧和右侧的乘积；常数动态记录从右往左依次右侧所有元素的乘积。

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:n = len(nums)answer = [1] * n# 下标i（不含）左侧所有元素的乘积for i in range(1, n):answer[i] = answer[i - 1] * nums[i - 1]# 记录右侧所有元素乘积，初始为1multiply_right = 1# 除了下标i其他所有元素的乘积（左侧与右侧的乘积）for  i in range(n - 1, -1, -1):answer[i] = answer[i] * multiply_rightmultiply_right *= nums[i]return answer

3、（难度：困难）

【Python3】

解题思路：一个列表记录前缀和（从开头到对应下标之前的合计，第一个元素为0），一个常数动态记录最短子数组长度（初始为原始数组nums的长度+1），一个双端队列动态记录下标。

依次遍历前缀和列表的元素，① 依次缩减左侧元素，查找该元素所在的最短子数组并记录最短长度，② 依次从双端队列右侧，对应前缀和列表中的元素大于等于当前元素的，删除双端队列右侧即最后一个元素（放入双端队列的下标，对应的前缀和将会作为后续某个下标的前缀和的减数，来获得该某下标的最短子数组，减数越大，子数组和越难达到k）。

遍历完前缀和列表，若最短子数组长度不是初始值，即存在最短子数组 返回最短长度，否则没有最短子数组 返回-1。

知识点：collections.deque()：双端队列，两端都可以进出。

              双端队列.popleft()：删除双端队列左侧（开头）的第一个元素，并返回该元素。

              双端队列.pop()：删除双端队列右侧（末尾）的第一个元素，并返回该元素。

              双端队列.append(元素)：往双端队列右侧（末尾）添加元素。

class Solution:def shortestSubarray(self, nums: List[int], k: int) -> int:n = len(nums)# 前缀和列表，第一个元素为0res_prev =[0]# 最短子数组长度，初始为n+1res = n + 1# 记录前缀和for x in nums:res_prev.append(res_prev[-1] + x)import collections# 双端队列，记录下标q = collections.deque()# 遍历前缀和列表for i, val in enumerate(res_prev):# 大于k的子数组依次缩减左侧元素，记录最短长度while q and val - res_prev[q[0]] >= k:res = min(res, i - q.popleft())# 依次从双端队列右侧，对应的前缀和大于等于当前前缀和，删除双端队列右侧即最后一个元素while q and res_prev[q[-1]] >= val:q.pop()# 往双端队列末尾添加下标q.append(i)# 最短长度不是初始值，则有最短子数组返回长度，否则没有最短子数组return res if res < n + 1 else -1