718. 最长重复子数组
题目描述
输入两个整数数组 nums1 和 nums2。
子数组指数组中连续的一段。找出同时出现在两个数组中的最长子数组，返回它的长度。没有公共元素时返回 0。
示例 1
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3
解释：两个数组都含有连续片段 [3,2,1]，长度为 3。
示例 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
解题思路：二维动态规划
dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度。两个结尾元素相等时，可以接在左上角那段的后面：dp[i][j] = dp[i-1][j-1] + 1；不相等时为 0，因为子数组必须连续。答案是整张表的最大值。在表中，一段公共子数组就是一条斜线。
为什么正确
计算 dp[i][j] 时，左上角 dp[i-1][j-1] 已经算好；best 是已算格子中的最大值。
复杂度分析
时间 O(mn)，空间 O(mn)（可以压缩到 O(n)）。
易错点
这是子数组（连续），不是子序列：不相等时是 0，而不是 max(dp[i-1][j], dp[i][j-1])。答案也不是 dp[m][n]，而是全表最大值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
best = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
best = max(best, dp[i][j])
return bestclass Solution {
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int[][] dp = new int[m + 1][n + 1];
int best = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
best = Math.max(best, dp[i][j]);
}
}
}
return best;
}
}class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
int best = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
best = max(best, dp[i][j]);
}
}
}
return best;
}
};func findLength(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
best := 0
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if nums1[i-1] == nums2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
best = max(best, dp[i][j])
}
}
}
return best
}var findLength = function(nums1, nums2) {
const m = nums1.length, n = nums2.length;
const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
let best = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
best = Math.max(best, dp[i][j]);
}
}
}
return best;
};function findLength(nums1: number[], nums2: number[]): number {
const m = nums1.length, n = nums2.length;
const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
let best = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
best = Math.max(best, dp[i][j]);
}
}
}
return best;
}其他解法
动态规划最直观；滑动对齐把空间降到 O(1)；二分 + 滚动哈希把时间降到近线性，但依赖哈希不冲突。
解法 2：滑动对齐 时间 O((m+n)·min(m,n))，空间 O(1)
把两个数组错开不同的偏移量对齐。对每种对齐方式，同时扫描重叠部分，统计连续相等元素的最长长度。nums1 相对 nums2 右移和左移的所有偏移量都要枚举。
时间与动态规划同阶，但只用 O(1) 额外空间。代码要处理两个方向的偏移，比动态规划多一些边界细节。
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
def scan(i, j, length):
best = cur = 0
for k in range(length):
if nums1[i + k] == nums2[j + k]:
cur += 1
best = max(best, cur)
else:
cur = 0
return best
best = 0
for i in range(m):
best = max(best, scan(i, 0, min(m - i, n)))
for j in range(n):
best = max(best, scan(0, j, min(n - j, m)))
return bestclass Solution {
int scan(int[] a, int[] b, int i, int j, int len) {
int best = 0, cur = 0;
for (int k = 0; k < len; k++) {
if (a[i + k] == b[j + k]) {
cur++;
best = Math.max(best, cur);
} else {
cur = 0;
}
}
return best;
}
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length, best = 0;
for (int i = 0; i < m; i++) best = Math.max(best, scan(nums1, nums2, i, 0, Math.min(m - i, n)));
for (int j = 0; j < n; j++) best = Math.max(best, scan(nums1, nums2, 0, j, Math.min(n - j, m)));
return best;
}
}class Solution {
public:
int scan(vector<int>& a, vector<int>& b, int i, int j, int len) {
int best = 0, cur = 0;
for (int k = 0; k < len; k++) {
if (a[i + k] == b[j + k]) {
cur++;
best = max(best, cur);
} else {
cur = 0;
}
}
return best;
}
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size(), best = 0;
for (int i = 0; i < m; i++) best = max(best, scan(nums1, nums2, i, 0, min(m - i, n)));
for (int j = 0; j < n; j++) best = max(best, scan(nums1, nums2, 0, j, min(n - j, m)));
return best;
}
};func findLength(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)
scan := func(i, j, length int) int {
best, cur := 0, 0
for k := 0; k < length; k++ {
if nums1[i+k] == nums2[j+k] {
cur++
if cur > best {
best = cur
}
} else {
cur = 0
}
}
return best
}
best := 0
for i := 0; i < m; i++ {
if v := scan(i, 0, min(m-i, n)); v > best {
best = v
}
}
for j := 0; j < n; j++ {
if v := scan(0, j, min(n-j, m)); v > best {
best = v
}
}
return best
}var findLength = function(nums1, nums2) {
const m = nums1.length, n = nums2.length;
const scan = (i, j, len) => {
let best = 0, cur = 0;
for (let k = 0; k < len; k++) {
if (nums1[i + k] === nums2[j + k]) {
cur++;
best = Math.max(best, cur);
} else {
cur = 0;
}
}
return best;
};
let best = 0;
for (let i = 0; i < m; i++) best = Math.max(best, scan(i, 0, Math.min(m - i, n)));
for (let j = 0; j < n; j++) best = Math.max(best, scan(0, j, Math.min(n - j, m)));
return best;
};function findLength(nums1: number[], nums2: number[]): number {
const m = nums1.length, n = nums2.length;
const scan = (i: number, j: number, len: number): number => {
let best = 0, cur = 0;
for (let k = 0; k < len; k++) {
if (nums1[i + k] === nums2[j + k]) {
cur++;
best = Math.max(best, cur);
} else {
cur = 0;
}
}
return best;
};
let best = 0;
for (let i = 0; i < m; i++) best = Math.max(best, scan(i, 0, Math.min(m - i, n)));
for (let j = 0; j < n; j++) best = Math.max(best, scan(0, j, Math.min(n - j, m)));
return best;
}解法 3：二分 + 滚动哈希 时间 O((m+n)·log min(m,n))，空间 O(m)
如果长度为 L 的公共子数组存在，那么更短的也存在，所以可以二分答案 L。检查时用滚动哈希算出 nums1 所有长度为 L 的子数组的哈希值放入集合，再滚动扫描 nums2，看是否有哈希值命中。
时间复杂度最低，适合数组很长的情况。哈希有极小的冲突概率，需要选好底数和模数。
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
MOD, BASE = 10**9 + 9, 113
def hashes(a, L, pw):
h = 0
for k in range(L):
h = (h * BASE + a[k]) % MOD
out = [h]
for i in range(L, len(a)):
h = ((h - a[i - L] * pw) * BASE + a[i]) % MOD
out.append(h)
return out
def check(L):
if L == 0:
return True
pw = pow(BASE, L - 1, MOD)
seen = set(hashes(nums1, L, pw))
return any(h in seen for h in hashes(nums2, L, pw))
lo, hi = 0, min(len(nums1), len(nums2))
while lo < hi:
mid = (lo + hi + 1) // 2
if check(mid):
lo = mid
else:
hi = mid - 1
return loclass Solution {
static final long MOD = 1000000009L, BASE = 113;
long[] hashes(int[] a, int L, long pw) {
long[] out = new long[a.length - L + 1];
long h = 0;
for (int k = 0; k < L; k++) h = (h * BASE + a[k]) % MOD;
out[0] = h;
for (int i = L; i < a.length; i++) {
h = ((h - a[i - L] * pw % MOD + MOD) % MOD * BASE + a[i]) % MOD;
out[i - L + 1] = h;
}
return out;
}
boolean check(int[] nums1, int[] nums2, int L) {
if (L == 0) return true;
long pw = 1;
for (int k = 0; k < L - 1; k++) pw = pw * BASE % MOD;
Set<Long> seen = new HashSet<>();
for (long h : hashes(nums1, L, pw)) seen.add(h);
for (long h : hashes(nums2, L, pw)) {
if (seen.contains(h)) return true;
}
return false;
}
public int findLength(int[] nums1, int[] nums2) {
int lo = 0, hi = Math.min(nums1.length, nums2.length);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (check(nums1, nums2, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
}class Solution {
public:
const long long MOD = 1000000009, BASE = 113;
vector<long long> hashes(vector<int>& a, int L, long long pw) {
long long h = 0;
for (int k = 0; k < L; k++) h = (h * BASE + a[k]) % MOD;
vector<long long> out = {h};
for (int i = L; i < (int)a.size(); i++) {
h = ((h - a[i - L] * pw % MOD + MOD) % MOD * BASE + a[i]) % MOD;
out.push_back(h);
}
return out;
}
bool check(vector<int>& nums1, vector<int>& nums2, int L) {
if (L == 0) return true;
long long pw = 1;
for (int k = 0; k < L - 1; k++) pw = pw * BASE % MOD;
vector<long long> h1 = hashes(nums1, L, pw);
unordered_set<long long> seen(h1.begin(), h1.end());
for (long long h : hashes(nums2, L, pw)) {
if (seen.count(h)) return true;
}
return false;
}
int findLength(vector<int>& nums1, vector<int>& nums2) {
int lo = 0, hi = min(nums1.size(), nums2.size());
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (check(nums1, nums2, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
};func findLength(nums1 []int, nums2 []int) int {
const MOD, BASE = 1000000009, 113
hashes := func(a []int, L, pw int) []int {
h := 0
for k := 0; k < L; k++ {
h = (h*BASE + a[k]) % MOD
}
out := []int{h}
for i := L; i < len(a); i++ {
h = ((h-a[i-L]*pw%MOD+MOD)%MOD*BASE + a[i]) % MOD
out = append(out, h)
}
return out
}
check := func(L int) bool {
if L == 0 {
return true
}
pw := 1
for k := 0; k < L-1; k++ {
pw = pw * BASE % MOD
}
seen := map[int]bool{}
for _, h := range hashes(nums1, L, pw) {
seen[h] = true
}
for _, h := range hashes(nums2, L, pw) {
if seen[h] {
return true
}
}
return false
}
lo, hi := 0, min(len(nums1), len(nums2))
for lo < hi {
mid := (lo + hi + 1) / 2
if check(mid) {
lo = mid
} else {
hi = mid - 1
}
}
return lo
}var findLength = function(nums1, nums2) {
const MOD = 1000000009, BASE = 113;
const hashes = (a, L, pw) => {
let h = 0;
for (let k = 0; k < L; k++) h = (h * BASE + a[k]) % MOD;
const out = [h];
for (let i = L; i < a.length; i++) {
h = (((h - a[i - L] * pw % MOD + MOD) % MOD) * BASE + a[i]) % MOD;
out.push(h);
}
return out;
};
const check = (L) => {
if (L === 0) return true;
let pw = 1;
for (let k = 0; k < L - 1; k++) pw = pw * BASE % MOD;
const seen = new Set(hashes(nums1, L, pw));
return hashes(nums2, L, pw).some(h => seen.has(h));
};
let lo = 0, hi = Math.min(nums1.length, nums2.length);
while (lo < hi) {
const mid = (lo + hi + 1) >> 1;
if (check(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
};function findLength(nums1: number[], nums2: number[]): number {
const MOD = 1000000009, BASE = 113;
const hashes = (a: number[], L: number, pw: number): number[] => {
let h = 0;
for (let k = 0; k < L; k++) h = (h * BASE + a[k]) % MOD;
const out = [h];
for (let i = L; i < a.length; i++) {
h = (((h - a[i - L] * pw % MOD + MOD) % MOD) * BASE + a[i]) % MOD;
out.push(h);
}
return out;
};
const check = (L: number): boolean => {
if (L === 0) return true;
let pw = 1;
for (let k = 0; k < L - 1; k++) pw = pw * BASE % MOD;
const seen = new Set(hashes(nums1, L, pw));
return hashes(nums2, L, pw).some(h => seen.has(h));
};
let lo = 0, hi = Math.min(nums1.length, nums2.length);
while (lo < hi) {
const mid = (lo + hi + 1) >> 1;
if (check(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}