难度: Hard
Submission
运行时间: 1211 ms
内存: 83.4 MB
class Solution:
def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:
MOD = 10**9+7
n = len(nums1)
dp = [defaultdict(int) for _ in range(n)]
res = 0
for i in range(n):
dp[i][nums1[i]] += 1
dp[i][-nums2[i]] += 1
if i - 1 >= 0:
for preSum in dp[i - 1]:
dp[i][preSum + nums1[i]] += dp[i - 1][preSum]
dp[i][preSum + nums1[i]] %= MOD
dp[i][preSum - nums2[i]] += dp[i - 1][preSum]
dp[i][preSum - nums2[i]] %= MOD
res += dp[i][0]
res %= MOD
return res
Explain
这道题目的解法使用了动态规划（DP）与哈希表的结合。定义dp[i]为一个字典，其中键是从第一个元素到第i个元素的子数组可能的和，值是达到这个和的不同子数组的数量。对于每个元素nums1[i]和nums2[i]，更新dp[i]考虑两种情况：加上nums1[i]和减去nums2[i]。为了构建dp[i]，我们从dp[i-1]继承并更新。最后，我们累加所有dp[i]中和为0的情况，这代表从数组开头到当前位置的子数组和为0的数量。使用MOD来避免大数问题。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:
MOD = 10**9+7 # 定义模数防止整数溢出
n = len(nums1) # 数组长度
dp = [defaultdict(int) for _ in range(n)] # 初始化动态规划表
res = 0 # 结果初始化为0
for i in range(n): # 遍历每个元素
dp[i][nums1[i]] += 1 # 加上nums1[i]的情况
dp[i][-nums2[i]] += 1 # 减去nums2[i]的情况
if i - 1 >= 0: # 如果不是第一个元素
for preSum in dp[i - 1]: # 遍历前一个状态的所有可能的和
dp[i][preSum + nums1[i]] += dp[i - 1][preSum] # 更新和
dp[i][preSum + nums1[i]] %= MOD # 取模
dp[i][preSum - nums2[i]] += dp[i - 1][preSum] # 更新和
dp[i][preSum - nums2[i]] %= MOD # 取模
res += dp[i][0] # 如果当前的和为0，加到结果中
res %= MOD # 取模
return res # 返回结果
Explore
在动态规划中，dp[i]被定义为一个字典，是因为子数组的和的范围非常广，可能从很大的负数到很大的正数，这使得使用数组来存储所有可能的和变得不切实际，因为这会要求一个非常大的数组来覆盖所有可能的索引，导致空间复杂度极高且大部分值为空。使用字典可以动态地仅存储出现过的和及其次数，这样大大减少了空间的浪费，提高了空间效率。
从dp[i-1]更新到dp[i]的过程涉及遍历dp[i-1]中记录的所有可能的和，并基于这些和通过添加当前的nums1[i]和减去当前的nums2[i]来生成新的和。对于dp[i-1]中的每个和preSum，dp[i]中preSum + nums1[i]的计数增加dp[i-1][preSum]的值，同样地，dp[i]中preSum - nums2[i]的计数也增加dp[i-1][preSum]的值。这样，dp[i]不仅包含了由dp[i-1]产生的新的可能和，还包括了仅由nums1[i]和-num2[i]产生的和。
在数组的开始处，即i=0时，我们单独处理nums1[0]和-num2[0]，每个初始和的计数被设置为1。这意味着，即使在数组的开始，我们也考虑了子数组可以仅由一个元素组成的情况，即sum(nums1[0])和sum(-nums2[0])。从i=1开始，每个dp[i]都基于前一个dp[i-1]更新，并且每次更新时，如果和为0的情况出现，该情况被加入到最终结果中。这确保了即使是仅包含一个元素的子数组也被正确计数。
MOD值10^9+7是一个常用的大素数，它被广泛用于避免整数溢出的同时保持计算精度，特别是在算法竞赛和计算机科学中。这个数足够大，能够确保在大多数情况下计算不会溢出，同时由于是素数，它在数论中的一些特性（如模逆元的计算）也是有利的。使用不同的MOD值可能会影响计算的正确性和性能。如果MOD较小，可能会导致更频繁的溢出和结果错误；如果MOD非素数，还可能影响某些数学运算的正确性。