哈希算法题目：最长重复子数组 题目描述 给定两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。子数组要求是连续的。例如： 输入：nums1 = [ 1,2,3,2,1], nums2 = [ 3,2,1,4,7 ] 输出：3 解释：最长重复子数组为 [ 3,2,1 ]，长度为 3。 解题过程 1. 问题分析 子数组是连续序列，因此需要找到两个数组中连续相同的片段。暴力解法是枚举所有可能的子数组起点和长度，但时间复杂度为 O(n²×m)，效率低。我们可以结合哈希算法和二分查找优化。 2. 思路：哈希 + 二分查找 核心思想：如果存在长度为 k 的公共子数组，那么所有小于 k 的长度也一定存在。因此可以二分查找可能的最大长度 k。 哈希函数：对数组片段计算哈希值，通过比较哈希值判断是否相同。采用滚动哈希（如 Rabin-Karp 算法）快速计算子数组哈希。 3. 步骤详解 步骤 1：实现滚动哈希函数 选择基数 base 和模数 mod，减少哈希冲突。例如 base=113, mod=1e9+7。 对于数组 nums，其长度为 len 的子数组哈希值可通过公式计算： hash = (nums[i] * base^(len-1) + nums[i+1] * base^(len-2) + ... + nums[i+len-1]) % mod 滚动更新：已知前一个子数组哈希值 H，下一个子数组哈希值为： H' = (H * base - nums[i] * base^len + nums[i+len]) % mod 需处理负数： H' = (H' + mod) % mod 。 步骤 2：二分查找最大长度 设最小长度 left=0，最大长度 right=min(len(nums1), len(nums2))。 当 left < right 时： 取 mid = (left + right + 1) // 2（向上取整）。 检查是否存在长度为 mid 的公共子数组： 遍历 nums1 所有长度为 mid 的子数组，计算哈希值存入哈希集合。 遍历 nums2 所有长度为 mid 的子数组，若哈希值在集合中，说明存在。 如果存在，left = mid；否则 right = mid - 1。 最终 left 即为最长长度。 4. 示例演示 以 nums1 = [ 1,2,3,2,1], nums2 = [ 3,2,1,4,7 ] 为例： 二分查找：初始 left=0, right=5。 mid=3 时，nums1 的子数组 [ 3,2,1] 与 nums2 的 [ 3,2,1 ] 哈希值相同，存在公共子数组，left=3。 检查 mid=4：无公共子数组，right=3。循环结束，结果为 3。 5. 复杂度分析 时间复杂度：O((n+m) log min(n,m))，其中 n、m 为数组长度。 空间复杂度：O(n) 存储哈希集合。 6. 优化注意点 双哈希：使用两组 base 和 mod 减少冲突概率。 直接比较：哈希值匹配后，可进一步验证实际数组片段是否真相同（防止冲突）。