# 前缀和

### 常见场景

通常用于求子数组，特别是求正整数数组累加或者累乘的题型。

前缀和经常配合哈希表使用

### 解题思路

#### 累乘或者累加子数组

[724. 寻找数组的中心下标 - 力扣（Leetcode）](https://leetcode.cn/problems/find-pivot-index/description/)

#### 求子数组的个数时

可以用哈希表结构保存累加/累乘值，`map[sum]`的 值为累加或累乘为sum的个数。

代表题型：

[930. 和相同的二元子数组 - 力扣（Leetcode）](https://leetcode.cn/problems/binary-subarrays-with-sum/description/)

[974. 和可被 K 整除的子数组 - 力扣（Leetcode）](https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/)

[560. 和为 K 的子数组 - 力扣（Leetcode）](https://leetcode.cn/problems/subarray-sum-equals-k/)

#### 左右两侧累加/累乘

在某些条件下只能用左右前缀和解题，即从左到右累加一遍，再从右到左累加一遍，以此来解决某些题型。

正常情况下累加或者累乘一遍即可得到左侧和右侧的子数组累加和（或者乘积），以累加为例，左侧为`map[i-1]`，右侧为`total - map[i]` 。

[724. 寻找数组的中心下标 - 力扣（Leetcode）](https://leetcode.cn/problems/find-pivot-index/description/)

但是在某些条件下可能会限制，例如下面这题，禁止用除法，无法用total / map\[i]来获取i右侧的累乘值，因此需要左右两侧各累乘一遍。

[238. 除自身以外数组的乘积 - 力扣（Leetcode）](https://leetcode.cn/problems/product-of-array-except-self/)