718. 最长重复子数组
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
思路
动态规划
可以用dp[i][j]表示A数组从i位置，B数组从j位置开始的最长子数组长度，由此可知，当A[i] == B[j]时，dp[i][j]取决与dp[i+1][j+1]的结果，也即使dp[i][j] = dp[i+1][j+1]+1，当A[i] != B[j]时，dp[i][j] = 0。
代码
class Solution {
public:
int findLength(vector
<int>& A
, vector
<int>& B
) {
int m
= A
.size(), n
= B
.size();
vector
<vector
<int>> dp(m
+ 1, vector
<int>(n
+ 1, 0));
int ans
= 0;
for(int i
= m
- 1; i
>= 0; i
--) {
for(int j
= n
- 1; j
>= 0; j
--) {
if(A
[i
] == B
[j
]) {
dp
[i
][j
] = dp
[i
+ 1][j
+ 1] + 1;
}
else {
dp
[i
][j
] = 0;
}
ans
= max(ans
, dp
[i
][j
]);
}
}
return ans
;
}
};
滑动窗口
可以分别固定A数组让B数组滑动，固定B数组让A数组滑动，然后计算相对位置的重复元素即可。
代码
class Solution {
public:
int findMax(vector
<int>& A
, vector
<int>& B
, int index_A
, int index_B
, int len
) {
int len_return
= 0;
int k
= 0;
for(int i
= 0; i
< len
; i
++) {
if(A
[index_A
+ i
] == B
[index_B
+ i
]) {
k
++;
}
else {
k
= 0;
}
len_return
= max(k
, len_return
);
}
return len_return
;
}
int findLength(vector
<int>& A
, vector
<int>& B
) {
int m
= A
.size(), n
= B
.size();
int ans
= 0;
for(int i
= 0; i
< m
; i
++) {
int len
= min(m
- i
, n
);
int tmp
= findMax(A
, B
, i
, 0, len
);
ans
= max(ans
, tmp
);
}
for(int j
= 0; j
< n
; j
++) {
int len
= min(m
, n
- j
);
int tmp
= findMax(A
, B
, 0, j
, len
);
ans
= max(ans
, tmp
);
}
return ans
;
}
};
