算法之 前缀和

• 前缀和，就是定义pre 为nums的前i个元素的和值，一般pre数组长度会=n+1,如许在计算的nums数组中下标i到j的情况的时候，直接就可以使用pre[j+1]-pre,如果找的是第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[j+1] + pre[i+1][j] - pre[j] + nums[j]
  

前缀和基础

3427.变宗子数组求和

3427.变宗子数组求和

• 求解的是下标题目，以是是pre[j+1] - pre范例
  

1. class Solution:
2.     def subarraySum(self, nums: List[int]) -> int:
3.         # 前缀和的问题
4.         n = len(nums)
5.         pre = [0]*(n+1)
6.         for i in range(n):
7.             pre[i+1] = pre[i] + nums[i]
8.         ans = 0
9.         for i in range(n):
10.             start = max(0,i-nums[i])
11.             ans += pre[i+1] - pre[start]
12.         return ans

复制代码

前缀和与哈希表

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

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

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

1. class Solution:
2.     def numOfSubarrays(self, arr: List[int]) -> int:
3.         # 直接用哈希表存储
4.         mod = 10**9 + 7
5.         store = [0,0]
6.         n = len(arr)
7.         # 使用前缀和
8.         pre = [0]*(n+1)
9.         for i in range(n):
10.             pre[i+1] = pre[i] + arr[i]
11.         ans = 0
12.         for i in range(n+1):
13.             if pre[i] % 2==0:
14.                 ans = ans + store[1]
15.                 store[0] = store[0] + 1
16.             else:
17.                 ans = ans + store[0]
18.                 store[1] = store[1] + 1
19.         return ans % mod

复制代码

距离和

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

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

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

博主分析

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

复制代码

前缀异或和

1177.构建回文串检测

1177.构建回文串检测

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

1. class Solution:
2.     def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
3.         # 使用前缀和计算 26种字母出现的次数
4.         n = len(s)
5.         pre = [[0]*26 for i in range(n+1)]
6.         # 计数方式
7.         for i in range(n):
8.             tar = ord(s[i]) - ord("a")
9.             for j in range(26):
10.                 if j == tar:
11.                     pre[i+1][j] = pre[i][j] + 1
12.                 else:
13.                     pre[i+1][j] = pre[i][j]
14.         # 统计完成
15.         # 开始遍历
16.         m = len(queries)
17.         ans = [0]*m
18.         for i in range(m):
19.             odd = 0
20.             left,right,k = queries[i][0],queries[i][1],queries[i][2]
21.             for j in range(26):
22.                 # left 是下标，也就是第left+1个，那么就是对应pre[left],right是对应这个第right+1个,pre[right+1]
23.                 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):
24.                     odd += 1
25.             # 判断是否超过可以修改的次数
26.             if odd // 2 <= k:
27.                 ans[i] = True
28.             else:
29.                 ans[i] = False
30.         return ans

复制代码

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

1. class Solution:
2.     def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
3.         # 使用前缀和计算 26种字母出现的次数
4.         n = len(s)
5.         pre = [[0]*26 for i in range(n+1)]
6.         # 计数方式
7.         for i in range(n):
8.             tar = ord(s[i]) - ord("a")
9.             for j in range(26):
10.                 if j == tar:
11.                     pre[i+1][j] = pre[i][j] ^ 1
12.                 else:
13.                     pre[i+1][j] = pre[i][j] ^ 0
14.         # 统计完成
15.         # 开始遍历
16.         m = len(queries)
17.         ans = [0]*m
18.         for i in range(m):
19.             odd = 0
20.             left,right,k = queries[i][0],queries[i][1],queries[i][2]
21.             for j in range(26):
22.                 # left 是下标，也就是第left+1个，那么就是对应pre[left],right是对应这个第right+1个,pre[right+1]
23.                 #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):
24.                 if pre[right+1][j]%2 ^ pre[left][j]%2 == 1:
25.                     odd += 1
26.             # 判断是否超过可以修改的次数
27.             if odd // 2 <= k:
28.                 ans[i] = True
29.             else:
30.                 ans[i] = False
31.         return ans

复制代码

其他一维前缀和

1310.子数组异或查询

1310.子数组异或查询

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

1. class Solution:
2.     def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
4.         # 前缀异或和
5.         n = len(arr)
6.         pre = [0]*(n+1)
7.         for i in range(n):
8.             # pre[i] 表示前i个元素的异或和
9.             pre[i+1] = pre[i] ^ arr[i]
10.         m = len(queries)
11.         ans = [0]*m
12.         for i in range(m):
13.             left,right = queries[i][0],queries[i][1]
14.             # 对应的是第left+1到right+1的异或区间值，对应就是pre[right+1] - pre[left]
15.             ans[i] = pre[right+1] ^ pre[left]
16.         return ans

复制代码

二维前缀和

1314.矩阵地区和

1314.矩阵地区和

• 二维前缀和
  

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

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。