1、leetcode题目里对于元素加和的考察可谓是屡见不鲜，包括 简单的限定一个有效答案的两个或多个元素求和leetcode分类刷题：哈希表（Hash Table）（一、简单的两数之和）、在有序数组内对加和等于target的三元组、四元组等的求解leetcode分类刷题：基于数组的双指针（三、有序数组的元素求和）以及连续子数组加和leetcode分类刷题：滑动窗口（一、基本子数组类型）
2、本文总结的题型同样为对连续子数组加和进行考察，区别于leetcode分类刷题：滑动窗口（一、基本子数组类型）的是，数组元素为整数，不是正整数了，因此需要按照 前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）+哈希表 的思路进行解决，最后会发现这种题型就是leetcode分类刷题：哈希表（Hash Table）（一、简单的两数之和）的扩展，在解题模板上会有点类似
724. 寻找数组的中心下标
1、该题为典型的使用前缀和算法解决的问题，只需要两次遍历即可：第一次遍历求数组的和；第二次遍历求数组的前缀和，并判断对应位置是否为 中心下标
2、和1991. 找到数组的中间位置是完全一样的题目
from typing import List
'''
724. 寻找数组的中心下标
题目描述：给你一个整数数组nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例 1:
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
题眼：左侧右侧数组的和
思路1、三次遍历：第一次遍历建立从左到右的加和数组，第二次遍历建立从右到左的加和数组，第三次遍历对加和数组的对应位置判断相等情况
思路2、前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）：第一次遍历：求数组的和；第二次遍历：求数组的前缀和，并判断对应位置是否为 中心下标
'''
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
# 思路1、三次遍历
# leftSum = [0] * len(nums)
# s = 0
# for i in range(len(nums)):
# s += nums[i]
# leftSum[i] = s
# rightSum = [0] * len(nums)
# s = 0
# for i in range(len(nums) - 1, -1, -1):
# s += nums[i]
# rightSum[i] = s
# for i in range(len(leftSum)):
# if leftSum[i] == rightSum[i]:
# return i
# return -1
# 思路2、前缀和
# 第一次遍历：求数组的和
total = 0
for n in nums:
total += n
# 第二次遍历：求数组的前缀和，并判断对应位置是否为 中心下标
prefixSum = 0
for i in range(len(nums)):
prefixSum += nums[i]
if prefixSum * 2 - nums[i] == total: # 这个条件的判断没有想到！！
return i
return -1
if __name__ == "__main__":
obj = Solution()
while True:
try:
in_line = input().strip().split('=')
nums = [int(n) for n in in_line[1].split('[')[1].split(']')[0].split(',')]
print(obj.pivotIndex(nums))
except EOFError:
break
560. 和为 K 的子数组
1、通过题眼连续子数组来判断，该题很像是滑动窗口的解法，但数组元素为整数，不是正整数，不满足滑窗右边界增大元素之和递增、左指针增大元素之和递减 了
2、要用前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）+哈希表的思路！
3、通过这道题也认识到，如果“1. 两数之和”不是限定了样例只存在一个答案，其哈希表更新的逻辑有缺陷文章来源：https://www.toymoban.com/news/detail-686842.html
from typing import List
'''
560. 和为 K 的子数组
题目描述：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1:
输入：nums = [1,1,1], k = 2
输出：2
题眼：连续子数组，很像是滑动窗口的解法，但数组元素为整数，不是正整数，不满足滑窗右边界增大元素之和递增、左指针增大元素之和递减 了
思路：无法用滑动窗口了；要用前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）+哈希表的思路！
“1. 两数之和”的扩展：通过这道题也认识到，如果“1. 两数之和”不是限定了样例只存在一个答案，其哈希表更新的逻辑有缺陷
'''
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
result = 0
hashTable = {0: 1} # 这里保证了对 包含起始元素的连续子数组 的判断
prefixSum = 0
for n in nums: # 查找 以当前遍历元素n对应的索引位置为 右边界的连续子数组
prefixSum += n # 前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）
# 1、先找 以当前遍历元素n对应的索引位置 之前的前缀和是否存在满足条件的
if prefixSum - k in hashTable:
result += hashTable[prefixSum - k]
# 2、再将当前遍历元素n对应的索引位置 的前缀和添加到hashDict
if prefixSum not in hashTable:
hashTable[prefixSum] = 1
else:
hashTable[prefixSum] += 1
return result
if __name__ == "__main__":
obj = Solution()
while True:
try:
in_line = input().strip().split('=')
nums = [int(n) for n in in_line[1].split('[')[1].split(']')[0].split(',')]
k = int(in_line[2].strip())
print(obj.subarraySum(nums, k))
except EOFError:
break
974. 和可被 K 整除的子数组
1、“560. 和为 K 的子数组”的衍生题，思路为完全一致的前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）+哈希表
2、这道题比较难想的是使用 同余定理：两个除以k余数相等的数字，其差一定可以整除k，即 (preSumJ - preSumI)%K = 0 等价于 preSumJ%K == preSumI%K文章来源地址https://www.toymoban.com/news/detail-686842.html
from typing import List
'''
974. 和可被 K 整除的子数组
题目描述：给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。
子数组 是数组的 连续 部分。
示例 1:
输入：nums = [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]
题眼：连续子数组；“560. 和为 K 的子数组”的衍生题
思路：要用前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）+哈希表的思路
同时，需要使用 同余定理 (preSumJ - preSumI)%K = 0 等价于 preSumJ%K == preSumI%K
'''
class Solution:
def subarraysDivByK(self, nums: List[int], k: int) -> int:
# 需要用到 同余定理，两个除以k余数相等的数字，其差一定可以整除k
result = 0
hashTable = {0: 1} # 这里保证了对 包含起始元素的连续子数组 的判断
prefixSum = 0
for n in nums: # 查找 以当前遍历元素n对应索引位置为边界的连续子数组
prefixSum += n # 前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）
if prefixSum % k in hashTable:
result += hashTable[prefixSum % k]
hashTable[prefixSum % k] += 1
else:
hashTable[prefixSum % k] = 1
return result
if __name__ == "__main__":
obj = Solution()
while True:
try:
in_line = input().strip().split('=')
nums = [int(n) for n in in_line[1].split('[')[1].split(']')[0].split(',')]
k = int(in_line[2].strip())
print(obj.subarraysDivByK(nums, k))
except EOFError:
break
到了这里，关于leetcode分类刷题：哈希表（Hash Table）（四、前缀和 处理连续子数组）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
