算法之 前缀和

• 前缀和，就是定义pre[i] 为nums的前i个元素的和值，一般pre数组长度会=n+1,这样在计算的nums数组中下标i到j的情况的时候，直接就可以使用pre[j+1]-pre[i],如果找的是第i个到第j个，那么就是pre[j]-pre[i-1]
• 转化为第几个会好理解一点
• 所以得根据题目求解的是下标还是第几个确定具体的计算公式
• 前缀和与哈希表：注意第一个元素是否加入哈希表！
• 二维前缀和： 求解下标为(x1,y1),(x2,y2)二维区间之间的区间和，转化为第几个，那么对应的公式就是ans = pre[x2+1][y2+1] - pre[x1][y2+1] - pre[x2+1][y1] + pre[x1][y1],开始的时候求解的区间前缀的公式是pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + nums[i][j]

前缀和基础

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 = 0for 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 + 7store = [0,0]n = len(arr)# 使用前缀和pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i] + arr[i]ans = 0for i in range(n+1):if pre[i] % 2==0:ans = ans + store[1]store[0] = store[0] + 1else:ans = ans + store[0]store[1] = store[1] + 1return ans % mod

距离和

1685.有序数组中绝对值之和

1685.有序数组中绝对值之和

• 由于是有序的，所以计算的公式可以拆开，然后就会发现很多得使用到区间和的问题

博主分析

class Solution:def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:# 由于是有序的，所以可以考虑直接拆分公式，然后使用前缀和# 原本情况下，nums[i] - nums[j] 前面的情况，当 i的时候，前面有i个也就是# nums[i] * i - 前 nums[0] + ··· + nums[i-1] 也就是 pre[i]# n - 1 - (i+1) + 1 = n - i  -1 个 # 后续的情况就是 nums[j] - nums[i] ,也就是 nums[i+1] + ··· + nums[n-1] - # 第 i + 2个n = len(nums)pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i] + nums[i]ans = [0]*nfor i in range(n):ans[i] = i * nums[i] - pre[i] - (n-i-1)* nums[i] +  pre[n] - pre[i+1]return ans  

前缀异或和

1177.构建回文串检测

1177.构建回文串检测

• 可以看到，是求解区间的情况，并且可以重新排列，并且是最多K次替换成任何小写英文字母，对于回文串的问题，由于是可以重新排列，所以我们得统计每种字母出现的次数，因为当字母出现的次数是偶数的时候，我们就可以对称分布，当是奇数的时候，如果出现一个奇数，那我们可以直接放最中间，如果出现2个奇数，就得改变其中一个即可，以此类推我们只需统计区间内26个字母出现的奇数的次数num,那么对应结果就是num//2

class Solution:def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:# 使用前缀和计算 26种字母出现的次数n = len(s)pre = [[0]*26 for i in range(n+1)]# 计数方式for i in range(n):tar = ord(s[i]) - ord("a")for j in range(26):if j == tar:pre[i+1][j] = pre[i][j] + 1else:pre[i+1][j] = pre[i][j]# 统计完成 # 开始遍历m = len(queries)ans = [0]*m for i in range(m):odd = 0left,right,k = queries[i][0],queries[i][1],queries[i][2]for j in range(26):# left 是下标，也就是第left+1个，那么就是对应pre[left],right是对应这个第right+1个,pre[right+1]if (pre[right+1][j]%2 == 1 and  pre[left][j]%2 == 0) or (pre[right+1][j]%2 == 0 and  pre[left][j]%2 == 1):odd += 1# 判断是否超过可以修改的次数if odd // 2 <= k:ans[i] = Trueelse:ans[i] = Falsereturn ans

• 当然，这个奇数偶数的情况其实可以用异或的情况表示，也就是开始的时候都是0，但是该字母出现一次的时候，我们就用上一个次数前缀和异或1，否则就是异或0

class Solution:def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:# 使用前缀和计算 26种字母出现的次数n = len(s)pre = [[0]*26 for i in range(n+1)]# 计数方式for i in range(n):tar = ord(s[i]) - ord("a")for j in range(26):if j == tar:pre[i+1][j] = pre[i][j] ^ 1else:pre[i+1][j] = pre[i][j] ^ 0# 统计完成 # 开始遍历m = len(queries)ans = [0]*m for i in range(m):odd = 0left,right,k = queries[i][0],queries[i][1],queries[i][2]for j in range(26):# left 是下标，也就是第left+1个，那么就是对应pre[left],right是对应这个第right+1个,pre[right+1]#if (pre[right+1][j]%2 == 1 and  pre[left][j]%2 == 0) or (pre[right+1][j]%2 == 0 and  pre[left][j]%2 == 1):if pre[right+1][j]%2 ^ pre[left][j]%2 == 1:odd += 1# 判断是否超过可以修改的次数if odd // 2 <= k:ans[i] = Trueelse:ans[i] = Falsereturn ans

其他一维前缀和

1310.子数组异或查询

1310.子数组异或查询

• 异或的性质要掌握 a^b = k,那么就可以推出a = k ^ b
• 只需记录异或前缀即可，就类似于正常的求解区间和一样

class Solution:def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:# 前缀异或和n = len(arr)pre = [0]*(n+1)for i in range(n):# pre[i] 表示前i个元素的异或和pre[i+1] = pre[i] ^ arr[i]m = len(queries)ans = [0]*mfor i in range(m):left,right = queries[i][0],queries[i][1]# 对应的是第left+1到right+1的异或区间值，对应就是pre[right+1] - pre[left]ans[i] = pre[right+1] ^ pre[left]return ans

二维前缀和

1314.矩阵区域和

1314.矩阵区域和

• 二维前缀和

class Solution:def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:# 二维区间前缀和m,n = len(mat),len(mat[0])# 肯定不可能按照题目的意思直接构造# 还是按照二维前缀和的思想，求解答案pre = [[0]*(n+1) for _ in range(m+1)]for i in range(m):for j in range(n):# pre[i][j] 表示i列，前j行所围成的区间和pre[i+1][j+1] = pre[i+1][j] + pre[i][j+1] - pre[i][j] + mat[i][j]# 求解完，然后进行求解答案ans = [[0]*n for i in range(m)]for i in range(m):for j in range(n):# 先求解出下标的问题x1,x2 = max(0,i-k),min(m-1,i+k)y1,y2 = max(0,j-k),min(n-1,j+k)# 这个是下标问题，所以是对应的是ans[i][j] = pre[x2+1][y2+1] - pre[x2+1][y1] - pre[x1][y2+1] + pre[x1][y1]return ans