标签: 数组 二分查找 动态规划 滑动窗口 哈希函数 滚动哈希
难度: Medium
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出：5
提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100运行时间: 59 ms
内存: 16.2 MB
# # class Solution:
# # def findLength(self, nums1: List[int], nums2: List[int]) -> int:
# # dp=[[0 for _ in range(len(nums1)+1)] for _ in range(len(nums2)+1)]
# # ans=0
# # for i in range(1,len(nums1)+1):
# # for j in range(1,len(nums2)+1):
# # if nums1[i-1]==nums2[j-1]:
# # dp[i][j]=dp[i-1][j-1]+1
# # ans=max(ans,dp[i][j])
# # return ans
# class Solution:
# def findLength(self, nums1: List[int], nums2: List[int]) -> int:
# dp = [[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
# ans = 0
# for i in range(1,len(nums1)+1):
# for j in range(1,len(nums2)+1):
# if nums1[i-1] == nums2[j-1]:
# dp[i][j] = dp[i-1][j-1]+1
# ans = max(ans,dp[i][j])
# return ans
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
base, mod = 131, 10**9 + 9
def check(length: int) -> bool:
hashA = 0
for i in range(length):
hashA = (hashA * base + nums1[i]) % mod
bucketA = {hashA}
mult = pow(base, length - 1, mod)
for i in range(length, len(nums1)):
hashA = ((hashA - nums1[i - length] * mult) * base + nums1[i]) % mod
bucketA.add(hashA)
hashB = 0
for i in range(length):
hashB = (hashB * base + nums2[i]) % mod
if hashB in bucketA:
return True
for i in range(length, len(nums2)):
hashB = ((hashB - nums2[i - length] * mult) * base + nums2[i]) % mod
if hashB in bucketA:
return True
return False
left, right = 0, min(len(nums1), len(nums2))
ans = 0
while left <= right:
mid = (left + right) // 2
if check(mid):
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
这个题解使用了二分查找和滚动哈希的思路。首先定义了一个 check 函数，用于判断是否存在长度为 length 的公共子数组。check 函数中，分别计算 nums1 和 nums2 的长度为 length 的子数组的哈希值，并使用滚动哈希的方法快速计算出所有可能的子数组哈希值，然后判断是否存在相同的哈希值，如果存在则说明存在长度为 length 的公共子数组。接下来使用二分查找的方法，初始化 left 为 0，right 为 min(len(nums1), len(nums2))，然后进行二分查找，如果 check(mid) 为 True，说明存在长度为 mid 的公共子数组，则将 ans 更新为 mid，并将 left 更新为 mid + 1，否则将 right 更新为 mid - 1。最终返回 ans 即为最长重复子数组的长度。
时间复杂度: O((n + m) * log(min(n, m)))
空间复杂度: O(n)
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
base, mod = 131, 10**9 + 9
def check(length: int) -> bool:
hashA = 0
for i in range(length):
hashA = (hashA * base + nums1[i]) % mod
bucketA = {hashA}
mult = pow(base, length - 1, mod)
for i in range(length, len(nums1)):
hashA = ((hashA - nums1[i - length] * mult) * base + nums1[i]) % mod
bucketA.add(hashA)
hashB = 0
for i in range(length):
hashB = (hashB * base + nums2[i]) % mod
if hashB in bucketA:
return True
for i in range(length, len(nums2)):
hashB = ((hashB - nums2[i - length] * mult) * base + nums2[i]) % mod
if hashB in bucketA:
return True
return False
left, right = 0, min(len(nums1), len(nums2))
ans = 0
while left <= right:
mid = (left + right) // 2
if check(mid):
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
在滚动哈希中，哈希冲突是指不同的数据生成了相同的哈希值。通常冲突的处理方式包括使用双哈希或更复杂的数据结构来减少冲突概率。在本题解中，没有特殊机制直接处理哈希冲突。题解依赖单一的哈希函数和大的模数来尽力减少冲突，但如果真的发生冲突，则可能会错误地认为两个不同的子数组相同。因此，虽然使用滚动哈希在大多数情况下效率高且错误率低，但它并不能完全保证不出现误判。
在滚动哈希中，`base` 和 `mod` 的选择对哈希函数的性能和冲突率有重要影响。`base` 通常选择一个与数据规模相关的较大素数，以确保数据被均匀映射，减少哈希碰撞的概率。`mod` 通常也选择一个大素数，这样可以使得哈希值均匀分布在一个大的范围内，进一步减少碰撞。在本题解中，`base` 选择为 131，`mod` 为 10**9 + 9，这是常用的组合，可以在处理大规模数据时保持较好的性能和较低的冲突概率。
二分查找在这里被用于优化查找最长公共子数组的长度，因为它可以有效地缩小搜索范围，从而减少不必要的计算。动态规划也是解决此类问题的一种常见方法，特别是在空间复杂度可以接受的情况下，它可以提供确切的结果。然而，动态规划的时间和空间复杂度通常是 O(n*m)，对于大数据量可能不够高效。因此，如果问题允许一定的误差（如可能的哈希冲突），二分查找配合滚动哈希可以提供更快的解决方案。
在二分查找中，当`check(mid)`返回True，意味着至少存在一个长度为`mid`的公共子数组。此时，为了查找是否存在更长的公共子数组，需要将搜索范围向更大的长度调整，即将`left`设置为`mid + 1`。这样做是为了尝试找到可能存在的更长子数组，而不是停留在当前已找到的长度。如果`mid`已经是最长长度，随后的查找将自然无法找到更长的，最终`left`将超过`right`，循环结束，返回之前找到的最大值。