昨日回顾
昨天的数组专题，我们针对双指针中的特殊场景----滑动窗口思维进行了学习。
在解题思维中，罗列出了滑动窗口的模板的使用方式，通过：
- 确定左右边界
- 查找窗口滑动条件的方式
- 按照题意套模板
即可可以轻松解决滑窗相关的题目。
滑动窗口的力所不及
在套模板的同时，大家是否考虑过，假设题目同样是求连续的子数组，但是在数组中出现了负数，那这种情况下还可以使用滑动窗口么？
答案是不行的，为什么？
我们窗口滑动的条件是什么，while窗口内元素超过或者不满足条件时移动，但如果数组存在负数，遇到不满足题意的时候，我们应该移动窗口左边界，还是扩大窗口右边界从而寻找到符合条件的情况呢？
当一种场景存在多种可能时，显然就是当前的算法不适配解题。今天就为大家介绍另一种数组中常用的算法----前缀和。
前缀和的解题思想
前缀和的题目解题思维比较固定，即当我们循环数组到下标N时，需要用到数组前N-1项的计算的结果（这里不一定非要是和，也可能是积等），此时我们就该考虑是否应该通过计算数组循环过程中的累计值的方式简化解题，如此便有了前缀和的解题思想。
了解了思想，下来就该考虑，这个累计的结果我们该通过什么方式保存起来呢？
- 题目明确要求不允许使用额外空间的，直接原地修改数组
- 不限制空间复杂度时，最好额外开辟空间计算，避免数据污染
- 计算时如果每次只需要获取前一次的累计结果，可以通过数组的方式存储每次获取数组末尾元素的值
- 如果每次计算需要获取前几次或更多次的结果进行对比时，推荐哈希表的方式，这样可以压缩时间复杂度
让我们先来通过一道题目，熟悉下前缀和的思维，并且了解下关于前缀和边界的这个易错点。
剑指OfferII010.和为k的子数组
https://leetcode-cn.com/problems/QTMn0o/solution/shua-chuan-jian-zhi-offer-day07-shu-zu-i-jdnu/
难度：中等
题目
给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
提示:
- 1 <= nums.length <= 2 * 10 ^ 4
- -1000 <= nums[i] <= 1000
- -10 ^ 7 <= k <= 10 ^ 7
示例
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2 :
输入:nums = [1,2,3], k = 3
输出: 2
分析
这道题目非常简洁，就是求数组中何为整数k的连续子数组个数。
如果这道题的取值没有负数，那就是标准的滑窗问题，但因为有了负数，滑窗思想不能用了。
通过分析，这道题应该属于我们上面列举四种情况的最后一种。具体思路如下：
- 初始化一个空的哈希表和pre_sum=0的前缀和变量
- 设置返回值ret = 0，用于记录满足题意的子数组数量
- 循环数组的过程中，通过原地修改数组的方式，计算数组的累加和
- 将当前累加和减去整数K的结果，在哈希表中查找是否存在
- 如果存在该key值，证明以数组某一点为起点到当前位置满足题意，ret加等于将该key值对应的value
- 判断当前的累加和是否在哈希表中，若存在value+1，若不存在value=1
- 最终返回ret即可
但在这里要注意刚才说到的前缀和边界问题。
我们在计算这种场景时，需要考虑如果以数组nums[0]为开头的连续子数组就满足题意呢？
此时候我们的哈希表还是空的，没办法计算前缀和！所以遇到这类题目，都需要在哈希表中默认插入一个{0:1}的键值对，
用于解决从数组开头的连续子数组满足题意的特殊场景。
下面就开始解题吧！
解题
Python:
class Solution:
def subarraySum(self, nums, k):
ret = pre_sum = 0
pre_dict = {0: 1}
for i in nums:
pre_sum += i
ret += pre_dict.get(pre_sum - k, 0)
pre_dict[pre_sum] = pre_dict.get(pre_sum, 0) + 1
return ret
Java:
class Solution {
public int subarraySum(int[] nums, int k) {
int pre_sum = 0;
int ret = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i : nums) {
pre_sum += i;
ret += map.getOrDefault(pre_sum - k, 0);
map.put(pre_sum, map.getOrDefault(pre_sum, 0) + 1);
}
return ret;
}
}
上面这道题，是一道标准的前缀和题目，并没有过多的去绕弯。
但如果你以为前缀和都是这么赤果果的出题，那真的错了。很多情况下，我们都需要对题目进行变化后，才能使用前缀和思想的。拿接下来这道题目说明。
剑指OfferII011.0和1个数相同的子数组
https://leetcode-cn.com/problems/A1NYOS/solution/shua-chuan-jian-zhi-offer-day07-shu-zu-i-4q9c/
难度：中等
题目
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
提示：
- 1 <= nums.length <= 105
- nums[i] 不是 0 就是 1
示例
示例 1:
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
分析
如果光看示例容易让我们误以为奇数下标为0，偶数下标为1，或者每两个下标长度判断一次结果等偏激的思想。
但当我们遇到连续0 或者连续1等特殊场景时，明显就不适用了。那么该如何变换后，可以适配前缀和的解题思维呢？
我们不妨将所有0转化为-1，那么如果遇到了相同数量的0和1，累加之后的结果就为0,不是就又转化为前缀和的思想了么？
解题思路如下：
- 初始化哈希表，并添加{0:-1}
- 声明前缀和变量pre_sum = 0，最大子数组长度返回值ret = 0
- 循环数组，若元素为0，pre_sum - 1,反之pre_sum + 1
- 判断哈希表中是否存在值为pre_sum的key
- 若存在pre_sum的key,更新ret为max(ret, 当前下标 - key对应的value + 1)
- 最终返回ret即可
解题
Python:
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
pre_dict = {0: -1}
ret = pre_sum = 0
for index, num in enumerate(nums):
pre_sum += -1 if num == 0 else 1
if pre_sum in pre_dict:
ret = max(ret, index - pre_dict[pre_sum])
else:
pre_dict[pre_sum] = index
return ret
Java
class Solution {
public int findMaxLength(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int pre_sum = 0;
int ret = 0;
for (int i = 0; i < nums.length; i++) {
pre_sum += nums[i] == 0 ? -1 : 1;
if (map.containsKey(pre_sum)) {
ret = Math.max(ret, i - map.get(pre_sum));
} else {
map.put(pre_sum, i);
}
}
return ret;
}
}
前缀和题目推荐
今天的题目学习就到这里，如果大家学有余力，可以看看其他变种的题目：
- 713.乘积小于K的子数组（前缀积了解一下）
- 1004.最大连续1的个数 III
或者在力扣题库中选择前缀和标签，来一次通杀。
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
网友评论