五分钟学算法：前缀和系列

迈不过友情╰ 2023-01-08 02:27 158阅读 0赞

![format_png][]

今天我们来说一下刷题时经常用到的**前缀和**思想，**前缀和**和**滑动窗口**会经常用在求**子数组和子串**问题上，当我们遇到此类问题时，则应该首先想到此类解题方式，该文章会深入浅出描述前缀和，读完这个文章就会有**属于自己的解题框架**，遇到此类问题时就能够轻松应对，我个人建议做题时不要背代码模板，应该自己进行总结，下次遇到时自然而然就能写出了。

![format_png 1][]

下面我们先来了解一下**什么是前缀和**。

前缀和其实我们很早之前就了解过的，我们求数列的和时，Sn = a1+a2+a3+...an; 此时Sn就是数列的**前 n 项和**。例 S5 = a1 + a2 + a3 + a4 + a5; S2 = a1 + a2。所以我们完全可以通过 S5-S2 得到 a3+a4+a5 的值，这个过程就和我们做题用到的前缀和思想类似。我们的前缀和数组里保存的就是**前 n 项的和**。见下图

![format_png 2][]

我们通过前缀和数组保存**前 n 位的和**，presum\[1\]保存的就是 nums 数组中前 1 位的和，也就是 **presum\[1\]** = nums\[0\], **presum\[2\]** = nums\[0\] + nums\[1\] = **presum\[1\]** \+ nums\[1\]. 依次类推，所以我们通过前缀和数组可以轻松得到每个区间的和。

例如我们需要获取 nums\[2\] 到 nums\[4\] 这个区间的和，我们则可以完全根据 **presum 数组**得到，是不是有点和我们之前说的字符串匹配算法中 BM,KMP 中的 next 数组和 suffix 数组作用类似。那么我们怎么根据 presum 数组获取 nums\[2\] 到 nums\[4\] 区间的和呢？见下图

![format_png 3][]

好啦，我们已经了解了前缀和的解题思想了，我们可以通过下面这段代码得到我们的**前缀和数组**，非常简单

![format_png 4][]

好啦，我们开始实战吧。

### leetcode 724. 寻找数组的中心索引 ###

**题目描述**

> 给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。
> 
> 我们是这样定义数组 中心索引 的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
> 
> 如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

**示例 1：**

> 输入：nums = \[1, 7, 3, 6, 5, 6\] 输出：3

解释：索引 3 (nums\[3\] = 6) 的左侧数之和 (1 + 7 + 3 = 11)，与右侧数之和 (5 + 6 = 11) 相等。同时, 3 也是第一个符合要求的中心索引。

**示例 2：**

> 输入：nums = \[1, 2, 3\] 输出：-1

解释：数组中不存在满足此条件的中心索引。

**解析**

理解了我们前缀和的概念（不了解好像也可以做，这个题太简单了哈哈）。我们可以一下就能把这个题目做出来，先遍历一遍求出数组的和，然后第二次遍历时，直接进行对比左半部分和右半部分是否相同，如果相同则返回 true，不同则继续遍历。

![format_png 5][]

### leetcode 560. 和为K的子数组 ###

**题目描述**

> 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

**示例 1 :**

> 输入:nums = \[1,1,1\], k = 2 输出: 2 , \[1,1\] 与 \[1,1\] 为两种不同的情况。

**暴力法**

**解析**

我们先来用暴力法解决这个题目，很简单，一下就能 AC。

这个题目的题意很容易理解，就是让我们返回和为 k 的子数组的个数，所以我们直接利用双重循环解决该题，这个是很容易想到的。我们直接看代码吧。

![format_png 6][]

好啦，既然我们已经知道如何求**前缀和数组**，那我们来看一下如何用前缀和数组来解决这个问题。

![format_png 7][]

我们分析上面的代码，发现该代码虽然用到了前缀和数组，但是对比暴力法并没有提升性能，时间复杂度仍为O(n^2)，空间复杂度却成了 O(n)。那我们有没有其他方法解决呢？

**前缀和 + HashMap**

了解这个方法前，我们先来看一下下面这段代码，保证你很熟悉

![format_png 8][]

上面的这段代码是不是贼熟悉，没错就是那个快被我们做烂的两数之和。这一段代码就是用到了我们的前缀和+ HashMap 思想，那么我们如何通过这个方法来解决这个题目呢？

在上面的代码中，我们将数组的值和索引存入 map 中，当我们遍历到某一值 x 时，判断 map 中是否含有 target - x，即可。

其实我们现在这个题目和两数之和原理是一致的，只不过我们是将所有的前缀和该前缀和出现的次数存到了 map 里。下面我们来看一下代码的执行过程。

我们来拆解一下动图，可能有的同学会思考为什么我们只要查看是否含有 presum - k ，并获取到presum - k 出现的次数就行呢？见下图

![format_png 9][]

因为我们此时 presum 已知，如果知道了presum - k 的个数，也就知道了 k 的个数。所以我们完全可以通过 presum - k的个数获得 k 的个数

好啦我们来看一下代码吧

![format_png 10][]

做完这个题目，各位也可以去完成一下这个题目，两个题目几乎完全相同 **leetcode 930. 和相同的二元子数组**

### leetcode1248. 统计「优美子数组」 ###

**题目描述**

> 给你一个整数数组 nums 和一个整数 k。
> 
> 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
> 
> 请返回这个数组中「优美子数组」的数目。

**示例 1：**

> 输入：nums = \[1,1,2,1,1\], k = 3 输出：2 解释：包含 3 个奇数的子数组是 \[1,1,2,1\] 和 \[1,2,1,1\] 。

**示例 2：**

> 输入：nums = \[2,4,6\], k = 1 输出：0 解释：数列中不包含任何奇数，所以不存在优美子数组。

**示例 3：**

> 输入：nums = \[2,2,2,1,2,2,1,2,2,2\], k = 2 输出：16

如果上面那个题目我们完成了，这个题目做起来，分分钟的事，不信你去写一哈，百分百就整出来了，我们继续按上面的思想来解决。

**前缀和** **+ HashMap**

**解析**

上个题目我们是求和为 K 的子数组，这个题目是让我们求 恰好有 k 个奇数数字的连续子数组，这两个题几乎是一样的，上个题中我们将前缀区间的和保存到哈希表中，这个题目我们只需将前缀区间的奇数个数保存到区间内即可，只不过将 sum += x 改成了判断奇偶的语句，见下图。

![format_png 11][]

我们来解析一下哈希表，key 代表的是含有 1 个奇数的前缀区间，value 代表这种子区间的个数，含有两个，也就是nums\[0\],nums\[0,1\].后面含义相同，那我们下面直接看代码吧，一下就能读懂。

![format_png 12][]

但是也有一点不同，就是我们是**统计奇数的个数**，数组中的奇数个数肯定不会超过原数组的长度，所以这个题目中我们可以用数组来**模拟 HashMap** ，用数组的**索引来模拟 HashMap 的 key**，用**值来模拟哈希表的 value**。下面我们直接看代码吧。

![format_png 13][]

### leetcode 974 和可被 K 整除的子数组 ###

**题目描述**

> 给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

**示例：**

> 输入：A = \[4,5,0,-2,-3,1\], K = 5 输出：7

**解释：**

> 有 7 个子数组满足其元素之和可被 K = 5 整除：\[4, 5, 0, -2, -3, 1\], \[5\], \[5, 0\], \[5, 0, -2, -3\], \[0\], \[0, -2, -3\], \[-2, -3\]

**前缀和+HashMap**

**解析**

我们在该文的第二题 **和为K的子数组** 中，我们需要求出满足条件的区间，见下图

![format_png 9][]

我们需要找到满足，和为 K 的区间。我们此时 **presum** 是已知的，k 也是已知的，我们只需要**找到 presum - k 区间的个数**，就能得到 k 的区间个数。但是我们在当前题目中应该怎么做呢？见下图。

![format_png 14][]

我们在之前的例子中说到，**presum\[j+1\] - presum\[i\] 可以得到 nums\[i\] + nums\[i+1\]+.... nums\[j\]**，也就是**\[i,j\]区间的和**。

那么我们想要判断区间 \[i,j\] 的和是否能整除 K，也就是上图中红色那一段是否能整除 K，那么我们只需判断

(presum\[j+1\] - presum\[i\] ) % k 是否等于 0 即可，

我们假设 (presum\[j+1\] - presum\[i\] ) % k == 0；则

presum\[j+1\] % k - presum\[i\] % k == 0;

presum\[j +1\] % k = presum\[i\] % k ;

我们 presum\[j +1\] % k 的值 key 是已知的，即是当前的 presum 和 k 的关系，所以我们只需要知道 **presum\[i\] 和 presum\[j+1\] % k 含有相同余数****时**，**i 有几种情况**。这样就能够知道当前能够整除 K 的区间个数。见下图

![format_png 15][]

**题目代码**

![format_png 16][]

我们看到上面代码中有一段代码是这样的

![format_png 17][]

这是为什么呢？不能直接用 presum % k 吗？

这是因为当我们 presum 为负数时，**需要对其纠正**。纠正前(-1) %2 = (-1)，纠正之后 ( (-1) % 2 + 2) % 2=1 保存在哈希表中的则为 1.则不会漏掉部分情况.

例如输入为 \[-1,2,9\],K = 2如果不对其纠正则会漏掉区间 \[2\] 此时 2 % 2 = 0，符合条件，但是不会被计数。

那么这个题目我们可不可以用数组，代替 map 呢？当然也是可以的，因为此时我们的哈希表存的是余数，余数最大也只不过是 K-1所以我们可以用固定长度 K 的数组来模拟哈希表。

![format_png 18][]

### leetcode 523 连续的子数组和 ###

**题目描述**

> 给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n\*k，其中 n 也是一个整数。

**示例 1：**

> 输入：\[23,2,4,6,7\], k = 6 输出：True

解释：\[2,4\] 是一个大小为 2 的子数组，并且和为 6。

**示例 2：**

> 输入：\[23,2,6,4,7\], k = 6 输出：True

解释：\[23,2,6,4,7\]是大小为 5 的子数组，并且和为 42。

**前缀和 + HashMap**

这个题目算是对刚才那个题目的升级，前半部分是一样的，都是为了让你找到能被 K 整除的子数组，但是**这里加了一个限制**，那就是**子数组的大小至少为 2**，那么我们应该怎么判断子数组的长度呢？我们可以根据索引来进行判断，见下图。

![format_png 19][]

此时我们 K = 6, presum % 6 = 4 也找到了相同余数的前缀子数组 \[0,1\] 但是我们此时**指针指向为 2**，我们的前缀子区间 \[0,1\]的**下界为1**，所以 2 - 1 = 1，但我们的中间区间的长度小于2，所以不能返回 true，需要继续遍历.

那我们有两个区间\[0,1\],\[0,2\]都满足 presum % 6 = 4，那我们哈希表中保存的下标应该是 1 还是 2 呢？我们保存的是1，如果我们保存的是较大的那个索引，则会出现下列情况，见下图。

![format_png 20][]

此时，仍会显示不满足子区间长度至少为 2 的情况，仍会继续遍历，但是我们此时的 \[2,3\] 区间**已经满足该情况**，应该返回 true，所以我们往哈希表存值时，只存一次，即最小的索引即可。下面我们看一下该题的两个细节

**细节1：**我们的 k 如果为 0 时怎么办，因为 0 不可以做除数。所以当我们 k 为 0 时可以直接存到数组里，例如输入为 \[0,0\] , K = 0 的情况

**细节2：**另外一个就是之前我们都是统计个数，value 里保存的是次数，但是此时我们加了一个条件就是长度至少为 2，保存的是索引，所以我们不能继续 map.put(0,1)，应该**赋初值为 map.put(0,-1)。**这样才不会漏掉一些情况，例如我们的数组为\[2,3,4\],k = 1,当我们 map.put(0,-1) 时，当我们遍历到 nums\[1\] 即 3 时，则可以返回 true，因为 1-（-1）= 2，5 % 1=0 , 同时满足。

**视频解析**

下面我们直接看代码吧，一下就能 整懂啦。

![format_png 21][]

![format_png 22][]

[format_png]: /images/20221119/1a5cb8e11e064d74b8d9673d402415e6.png
[format_png 1]: /images/20221119/fe3e7bb09d0d4503814b443da36e3e67.png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdtd2x3WTh4dnJSN1NsYTh4Vk95Tm5SSDVrNUFjNmF3ZTdaMDNxajlWYUI1NXphSGdsd2pCa3cvNjQw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVduZDI0Rmt1M2liZXF1MHFLT0xGT3FJemthaWFSN2hjRkZpY3lrN1R3VjluYmVIQlByazkxaWNGNmFnLzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVd6M2liRHpkMTJkaWJEMGljT3hsalpOZ2ljQk9OdFV1Uzg5MzF3OUx5SEhOR1o4YmZGcG45S3VJTThRLzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdpY0JOTkJLd0YxaWMzNU1hM2lhZEp4aHJGZjVnYm9EY201T0lxazhTdEc3REFDMjVBd1BqaWJXZm53LzY0MA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdDYzNUMWJseHA4YkZxZ25wY2lhYVVocFcwWXlHeFF3b2p0S1pqWlZwaWI3dmFzemNyd2ljUndzalEvNjQw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdQSU5aYmVvaWI1eTY1bmFOOFZOR0NQZ05CdHdaV1duRXhJOHp5TnpuTHppYVZsdXZJSTlyU2JEQS82NDA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdRMXNxMW05V1RWcldjcUVFa3hicThMUXZ5ZHhWa0NVN2ljU2RwbkNVazVmdDN0OE50SmtZRVpnLzY0MA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdpYVZub1VYRHYzRDVoS21mSFFONXJUM1k2eElCRUpHeDJwaWNxa253SFV6SE95cGtpYzNyWlpLWncvNjQw?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdFQkJhZElMU0VhRTU3OG1BS0t3NlNhMEVxaEJVMUxuR2tUaEdjckJvd2liclRybkdIeW81M2xBLzY0MA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdhUkFTc3ppYVYxcXpxMXkzSGJTdXQ3a2p3Q29scmJIYk1zdU1GVFVjaEZsaWJHWTJQTnU3aWFaaWJRLzY0MA?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdnbnh5MkVITWw1U2ljcUJ6VlNKd0tRRkZ3bXkxcFdiY2lhWkdCS0NSdjRpYUx1Q2ljZUhRcm9CWXF3LzY0MA?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdhMUViZk1zcmJzdDV0cWVYVUlWQ2NMUGd4OFM2czZLd2NnTVN5aWJ5bkp2YzVkaWFZRnNaVVRBQS82NDA?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdQeTFNTmJxSzlWWGlhcHp4NHVoNlNvSERFUktGR0RaVmZUaWFTOVg0Z3hsNHZRajl5Mmlja0t4elEvNjQw?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVc1eXlkeE4xcnVYNDJ2dXNuMkgxamxyUmljOEdkRTNJWVU3WXRFMWljclVjNjlLRlU1aWNRbzJLWmcvNjQw?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdIR2pONTJaeUhLZ2xIejRrNHNQYTVkT29xZnBRU045ajRSSGs4WWs0WFBlNnFvTWFZSllpYXNnLzY0MA?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdodVU3QzR1R1N5d0ZrbGUxbEFFYzJ5U0hMS250enNPcW9WdEhKNHlZd0NtbnM3bFFZWjNJV2cvNjQw?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVc1Z0hYdmlhRFhoejFlMHZwZkVDRkdjd3BSaWJBMHFRQ0lJVDBQMFBNSU9CZmtyaFpYNFFtSmJidy82NDA?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdFVnRNTHNMSDI5TGtJU3laamFodEFyQkl5b09vdTZFdExCWjFUUVpSelU1eTdNdloybzdMVHcvNjQw?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVdnM1hBeGRaUkxZZjBwVWljRnA5cFFZT2psTjlwYlVzeGhtMUNDS0Fhd2hsbGtSSURQRmM5ek5RLzY0MA?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9DbEFrVUlPaG90WEh2WW5VMW5TeEVFdHB0VDQ5RmliRVc4VjM0akZ0ZUh3ZFA2ZGNkb0FmdkxvbG5GcENLYVdGUUVqdjNtMmVkNGlhM2pEeGhVUlpKY3RRLzY0MA?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJmWVppY1YzWlV1M1o4M0Exa3MxWW9GenZqb0k5SGliRkZHTmF4RFRrTlkzUE9OczY3RWlhck1Kam0xd3p1TUJyTm1LWTRBNTRpYnNEd0lRLzY0MA?x-oss-process=image/format,png