目錄
-
-
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
-
1、題目
給兩個整數數組
A
和
B
，傳回兩個數組中公共的、長度最長的子數組的長度。
示例：
輸入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
輸出：3
解釋：
長度最長的公共子數組是 [3, 2, 1] 。
提示：
-
1 <= len(A), len(B) <= 1000
-
0 <= A[i], B[i] < 100
2、思路
(動态規劃) O ( n 2 ) O(n^2) O(n2)
狀态表示：
f[i][j]
表示長度為
i
，末尾項為
a[i-1]
的
a
數組，與長度為
j
，末尾項為
b[j-1]
的
b
數組的公共子數組的集合，屬性是最大長度。（
a
數組和
b
數組下标都是從
開始的，
f
數組下标從
1
開始）
集合劃分： 我們以末尾元素
a[i-1]
和
b[i-1]
是否相同劃分集合。
狀态計算：
如果長度為
i
，末尾項為
a[i-1]
的
a
數組和長度為
j
，末尾項為
b[j-1]
的
b
數組中的
a[i-1] == b[j-1]
。也就是說這兩個數組的末尾元素相等，那麼
f[i][j] = f[i-1][j-1] + 1
，
f[i][j]
可以由
f[i-1][j-1]
轉移而來；
否則
f[i][j] = 0
，表示以
a[i-1]
和
b[j-1]
為結尾的公共子數組的最大長度為
，因為其結尾元素不相等；
故狀态轉移方程為：
f[i][j] = f[i-1][j-1] + 1
，（
a[i-1] == b[j-1]
）
f[i][j] = 0
，（
a[i-1] != b[j-1]
）
細節：
- 初始化
f[i][0] = 0
f[0][j] = 0
i
a
b
a
j
b
- 最終的答案為
res = max(res,f[i][j])
a
b
完整分析圖示：
3、c++代碼
class Solution {
public:
int findLength(vector<int>& a, vector<int>& b) {
int n = a.size(), m = b.size();
vector<vector<int>> f(n + 1, vector<int> (m + 1, 0));
int res = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(a[i-1] == b[j-1])
f[i][j] = f[i-1][j-1] + 1;
else
f[i][j] = 0;
res = max(res, f[i][j]);
}
return res;
}
};
4、java代碼
class Solution {
public int findLength(int[] a, int[] b) {
int n = a.length;
int m = b.length;
int[][] f = new int[n+1][m+1];
int res = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(a[i-1] == b[j-1])
f[i][j] = f[i-1][j-1] + 1;
else
f[i][j] = 0;
res = Math.max(res, f[i][j]);
}
return res;
}
}
原題連結： 718. 最長重複子數組
