前缀和
常见场景
通常用于求子数组，特别是求正整数数组累加或者累乘的题型。
前缀和经常配合哈希表使用
解题思路
累乘或者累加子数组
求子数组的个数时
可以用哈希表结构保存累加/累乘值，map[sum]的 值为累加或累乘为sum的个数。
代表题型：
974. 和可被 K 整除的子数组 - 力扣（Leetcode）
左右两侧累加/累乘
在某些条件下只能用左右前缀和解题，即从左到右累加一遍，再从右到左累加一遍，以此来解决某些题型。
正常情况下累加或者累乘一遍即可得到左侧和右侧的子数组累加和（或者乘积），以累加为例，左侧为map[i-1]，右侧为total - map[i] 。
但是在某些条件下可能会限制，例如下面这题，禁止用除法，无法用total / map[i]来获取i右侧的累乘值，因此需要左右两侧各累乘一遍。
Last updated