基础前缀和
# 构建:s[i] 表示前 i 个元素之和,s[0] = 0
s = [0] * (n + 1)
for i in range(n):
s[i + 1] = s[i] + nums[i]
# 查询区间 [l, r](闭区间,0-indexed)的和:
# nums[l] + ... + nums[r] = s[r + 1] - s[l]
range_sum = s[r + 1] - s[l]前缀和 + 哈希表 (和为 k 的子数组计数)
from collections import Counter
def subarraySum(nums, k):
ans = 0
prefix = 0
cache = Counter()
cache[0] = 1 # 空前缀,起跑线
for num in nums:
prefix += num
ans += cache[prefix - k] # 先查:有多少个更早的前缀能凑出 k
cache[prefix] += 1 # 后记:把当前前缀存入,供后续使用
return ans关键点:先查后记, 保证 cache 里只有当前下标之前的前缀，不会用到未来的前缀。
前缀和 + 哈希表 (最长 / 最短子数组)
def maxSubArrayLen(nums, k):
ans = 0
prefix = 0
first = {0: -1}
for i, num in enumerate(nums):
prefix += num
if prefix - k in first:
ans = max(ans, i - first[prefix - k])
if prefix not in first:
first[prefix] = i
return ans