什么是前缀和？leetcode例题解答

分手后的思念是犯贱 2022-09-11 08:15 166阅读 0赞

# 前缀和 #

假设给定数组\[1,1,1,1\]以及两个下标j k j<k，现在要你求j到k的所有数字的和，怎么做呢？我们当然可以根据这两个下标把对应的数字依次累加从而得到结果，这没问题，但如果我们要求很多个范围的和，这个数组也很大，每次都得从头开始累加就特别耗时了，有没有什么办法能从O(1)的时间复杂度直接得到结果，这就需要利用到前缀和。

假设我们有一个前缀和数组preSum，它和原数组的对应关系如下，也就是说我们通过一次遍历，已经知道了从下标0到每个下标 i 的元素和  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqR5LqR55qE5LqR_size_20_color_FFFFFF_t_70_g_se_x_16]  
那么现在，我们要知道下标1到下标3的元素和，扳指头都知道结果是3，但是站在presum的角度，其实我们可以知道是presum\[3\]-presum\[0\]，从而我们可以得到一个结论：

#### 要求任意j到k的元素和，其结果为 `presum[k]-presum[j-1]。` ####

通常 前缀和搭配哈希表使用

--------------------

## 例题1： ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqR5LqR55qE5LqR_size_18_color_FFFFFF_t_70_g_se_x_16]

*  每个元素对应一个“前缀和”
 *  遍历数组，根据当前“前缀和”，在 map 中寻找「与之相减 == k」的历史前缀和
 *  当前“前缀和”与历史前缀和，差分出一个子数组，该历史前缀和出现过 c 次，等价于当前项找到 c 个子数组求和等于 k。
 *  遍历过程中，c 不断加给 count，最后返回 count

## 例题2 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqR5LqR55qE5LqR_size_18_color_FFFFFF_t_70_g_se_x_16 1]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqR5LqR55qE5LqR_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3f8c394f52e54df4a193991ed5d65fc5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqR5LqR55qE5LqR_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e362e52076504e29969062b783f00808.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqR5LqR55qE5LqR_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/bde4914123924457a32912966ed0fb43.png