Leetcode【523、525、560、974】
Leetcode【523、525、560、974】
问题描述：【Hash Table】523. Continuous Subarray Sum
解题思路：
这道题是给一个非负整数数组和整数 k，判断数组是否含有连续子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
做法如下：
- 遍历整个数组，依次累加数组元素计算前缀和 presum，并将 presum 对 k 求余，求余结果只有 0~k-1 这 k 种情况（对 k 求余是为了满足题目中总和为 k 的倍数的说法）。然后，将求余结果存入 Hash Table 中，其中，键为求余结果，值为当前位置索引。
- 如果遍历到当前位置，presum 的求余结果已经在 Hash Table 中，表明从上一求余结果相同的位置到当前位置的子数组相加和是 k 的倍数，那么就判断当前位置和上一位置的差值是否大于等于 2 （题目要求），如果是，返回 True；否则将求余结果存入 Hash Table 中。
- 在初始化的时候，Hash Table 中要加入 {0: -1}，它是边界情况。
例1、以 nums = [2,4]，k = 3 举例：
- presum = 2，presum % 3 = 2，则 dic = {0: -1, 2: 0}；
- presum += 4 = 6，presum % 3 = 0，这时发现求余结果 0 在 Hash Table 中出现过，说明位置 (-1, 1] 之间的数字之和是 3 的倍数。并且发现两索引差值 i - dic[0] = 1 - (-1) = 2，大于等于 2，符合题意，返回 True。
例 1 也说明为什么要在初始化的时候在 Hash Table 中加入 {0: -1}。
例2、以 nums = [5,2,4]，k = 3 举例：
- presum = 5，presum % 3 = 2，则 dic = {0: -1, 2: 0}；
- presum += 2 = 4，presum % 3 = 1，则 dic = {0: -1, 2: 0, 1: 1}；
- presum += 4 = 5，presum % 3 = 2，这时发现求余结果 2 在 Hash Table 中出现过，说明位置 (0, 2] 之间的数字之和是 3 的倍数。并且发现两索引差值 i - dic[2] = 2 - 0 = 2，大于等于 2，符合题意，返回 True。
注意，这道题还有几个边界情况：（1）k 可能为负值和 0；（2）数组中可能出现 [0,0] 这种情况。
例3、以 nums = [0, 0]，k = 0 举例：
- presum = 0，因为 k 为 0， 所以不能进行取余操作，presum 结果还是 0 保持不变，这时发现结果 0 在 Hash Table 中出现过，说明位置 (-1, 0] 之间的数字之和是 0 的倍数。并且发现两索引差值 i - dic[0] = 0 - (-1) = 1，1 小于 2，不符合题意，则跳过，判断下一个位置。
- presum += nums[1] = 0，这时发现结果 0 在 Hash Table 中出现过，说明位置 (-1, 1] 之间的数字之和是 0 的倍数。并且发现两索引差值 i - dic[0] = 1 - (-1) = 2，1 大于等于 2，符合题意，返回 True。
考虑到上述 3 个例子的情况，我们就可以写出代码了。
Python3 实现：
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
dic = {0: -1} # 保存前缀和的位置索引，{0:-1}为了处理边界情况
presum = 0
for i in range(len(nums)):
presum += nums[i]
if k != 0: # k非0才对前缀和进行求余操作
presum %= k
if presum in dic: # 前缀和在dic中找到，说明当前位置与dic[presum]之间数字之和为k
if i - dic[presum] >= 2: # 还要满足长度大于等于2
return True
else:
dic[presum] = i
return False问题描述：【Hash Table】525. Contiguous Array
解题思路：
这道题是给一个 01 数组，求含有相同数量的 0 和 1 的最长连续子数组的长度。
方法1（前缀 01 差值）：
- 遍历数组的每个位置，统计数字 0 和 1 的个数，并计算前缀 01 差值；
- 如果该差值在后续还会出现，说明从上一位置到当前位置 01 个数相等，更新最大值；
- 如果该差值没有出现过，就保存在 Hash Table 中，键为差值，值为当前位置索引;
- 初始化时，将 {0: -1} 存入 Hash Table，便于边界情况判断。
例如，nums = [1,1,0,0,0,1]，cnt = [0, 0] 统计前缀 01 个数，对于每个位置 i：
- sub = cnt[0] - cnt[1] = -1，-1 不在 dic 中，则保存该差值 dic = {0: -1, -1: 0}；
- sub = cnt[0] - cnt[1] = -2，-2 不在 dic 中，则保存该差值 dic = {0: -1, -1: 0, -2: 1}；
- sub = cnt[0] - cnt[1] = -1，-1 在 dic 中，说明上一次出现 -1 差值的位置到当前位置，即区间 (0, 2] 之间的 01 个数相等，则更新最大长度 max_ = i - dic[-1] = 2 - 0 = 2；
- sub = cnt[0] - cnt[1] = 0，0 在 dic 中，说明上一次出现 0 差值的位置到当前位置，即区间 (-1, 3] 之间的 01 个数相等，则更新最大长度 max_ = i - dic[0] = 3 - (-1) = 4，这也是为什么要初始化 dic = {0: -1} 的原因；
- sub = cnt[0] - cnt[1] = 1，1 不在 dic 中，则保存该差值 dic = {0: -1, -1: 0, -2: 1, 1: 4}；
- sub = cnt[0] - cnt[1] = 2，2 不在 dic 中，则保存该差值 dic = {0: -1, -1: 0, -2: 1, 1: 4, 2: 5}；
- sub = cnt[0] - cnt[1] = 1，1 在 dic 中，则区间 (4, 6] 之间 01 个数相等，长度为 2，但是小于最大长度 max_，跳过。
- 最后得到最大长度 max_ = 4。
Python3 实现：
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
dic = {0: -1} # 保存01差值的位置索引，{0:-1}为了处理边界情况
cnt = [0, 0] # 统计01次数
max_ = 0
for k, num in enumerate(nums):
cnt[num] += 1 # 01计数
sub = cnt[0] - cnt[1] # 计算0与1的差值，可能为负值
if sub not in dic:
dic[sub] = k
else:
max_ = max(max_, k - dic[sub])
return max_方法2（前缀和为0）：
如果我们把数组中的所有 0 全部变成 -1，那么这道题就变成了求和为 0 的最长连续子数组长度。那么类似于上面的 Leetcode 523，我们计算前缀和，判断前缀和是否在 Hash Table 中再次出现，如果再次出现，说明两位置之间的和为 0，即两位置之间01个数相同，则更新最大长度；否则，将前缀和保存在 Hash Table 中。
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
dic = {0: -1} # 保存前缀和的位置索引，{0:-1}为了处理边界情况
presum, max_ = 0, 0
for k, num in enumerate(nums):
if num == 0: # 把0改成-1计算前缀和
presum += (-1)
else:
presum += 1
if presum not in dic:
dic[presum] = k
else: # 前缀和再次出现，说明两位置之间和为0，即01个数相等
max_ = max(max_, k - dic[presum])
return max_问题描述：【Hash Table】560. Subarray Sum Equals K
解题思路：
这道题是给一个数组，求连续子数组和为 k 的总数。
这道题和 Leetcode 523 以及 Leetcode 525 的方法 2 类似，也是先求前缀和 presum，但是区别在于，前面两道题判断 presum 是否再次出现在 Hash Table 中，但是这道题要判断 presum - k 是否再次出现在 Hash Table 中。并且，还有一点不同的是，因为要计算子数组的总数，所以 Hash Table 中的键还是前缀和 presum，但是值要存储当前前缀和出现的次数，而不像前两道题中存储当前位置索引。初始化时，Hash Table 中 {0: 1}，用于边界情况处理。
举个例子：nums = [2, 4, 1, 0, 5, -7]，k = 5
- presum = 2，2 - k 不在 dic 中，则把 presum 保存在 dic = {0: 1, 2: 1}；
- presum += 6，6 - k 不在 dic 中，则把 presum 保存在 dic = {0: 1, 2: 1, 6: 1}；
- presum += 7，7 - k 在 dic 中，说明上一次出现前缀和 2 的位置到当前位置之间的数字之和为 k，则 ans += dic[7-k] = 1，并把 presum 保存在 dic = {0: 1, 2: 1, 6: 1, 7: 1}；
- presum += 7，7 - k 在 dic 中，说明上一次出现前缀和 2 的位置到当前位置之间的数字之和为 k，则 ans += dic[7-k] = 2，并把 presum 保存在 dic = {0: 1, 2: 1, 6: 1, 7: 2}（前缀和 7 之前出现过一次，直接累加）；
- presum += 12，12 - k 在 dic 中，说明上一次出现前缀和 7 的位置到当前位置之间的数字之和为 k，则 ans += dic[12-k] = 4，并把 presum 保存在 dic = {0: 1, 2: 1, 6: 1, 7: 2, 12: 1}；
- presum += 5，5 - k 在 dic 中，说明上一次出现前缀和 0 的位置到当前位置之间的数字之和为 k，则 ans += dic[5-k] = 5，并把 presum 保存在 {0: 1, 2: 1, 6: 1, 7: 2, 12: 1, 5: 1}，这也是为什么初始化 Hash Table 为 {0: -1} 的原因；**
- 数组遍历完毕，ans = 5 就是答案。
Python3 实现：
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
dic = {0: 1} # 保存前缀和出现次数，{0:-1}为边界情况
presum, ans = 0, 0
for num in nums:
presum += num
if (presum - k) in dic: # 前缀和减去目标值在dic中找到，累加结果
ans += dic[presum-k]
if presum not in dic: # 将前缀和出现次数保存到dic中
dic[presum] = 1
else:
dic[presum] += 1
return ans问题描述：【Hash Table】974. Subarray Sums Divisible by K
解题思路：
这道题是给一个数组，求连续子数组之和可以被 K 整除的总数。
经过了上面三道题的历练，这道题自然很容易求解。题目中“连续子数组之和可以被 K 整除”类似于 Leetcode 523 的做法，要先将前缀和 presum 对 K 取余，并且判断 presum 是否在 Hash Table 中出现过；而它是一个计算总数的问题，类似于 Leetcode 560，Hash Table 中保存的应该是前缀和出现的次数。因此，很快可以写出代码。
Python3 实现：
class Solution:
def subarraysDivByK(self, A: List[int], K: int) -> int:
dic = collections.defaultdict(int)
dic[0] = 1
ans, presum = 0, 0
for a in A:
presum += a
presum %= K # 先将前缀和对K取余
if presum in dic:
ans += dic[presum]
dic[presum] += 1 # 统计前缀和出现次数
return ans总结：
计算数组前缀（前缀和、前缀01差值、前缀和对K的取余结果等等）保存在 Hash Table 中，等到下次再次出现相同的前缀时，说明两次位置之间的数字是满足题意的。利用这个特点，我们能做到在 O(n) 的时间内求解。