leetcode 718. 最长重复子数组
题目详情
题目链接 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 1: 输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。
说明:
1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100
我的代码
class Solution {
public:
int findLength(vector
<int>& A
, vector
<int>& B
) {
int aLen
= A
.size(), bLen
= B
.size();
set
<int> bSet(B
.begin(), B
.end());
int res
= 0;
for (int i
= 0; i
< aLen
- res
; ++i
) {
if (bSet
.count(A
[i
]) == 0) {
continue;
}
for (int j
= 0; j
< bLen
- res
; ++j
) {
if (A
[i
] == B
[j
]) {
int ans
= 1;
for (int ii
= i
+ 1, jj
= j
+ 1; (ii
< aLen
) && (jj
< bLen
); ++ii
, ++jj
) {
if (A
[ii
] != B
[jj
]) {
break;
}
++ans
;
}
res
= max(res
, ans
);
}
}
}
return res
;
}
};
我的成绩
执行结果：通过 执行用时：876 ms, 在所有 C++ 提交中击败了5.00%的用户 内存消耗：11.6 MB, 在所有 C++ 提交中击败了100.00%的用户
一些想法
本道题我用得暴力法，在此基础上做了些优化，应该有更好的算法。
执行用时为 52 ms 的范例
class Solution {
public:
int findLength(vector
<int>& a
, vector
<int>& b
) {
int size1
= a
.size(), size2
= b
.size();
if (size1
== 0 || size2
== 0) return 0;
if (size1
< size2
) return findLength(b
, a
);
vector
<unsigned int> hash_a(size1
+ 1, 0), hash_b(size2
+ 1, 0), power(size2
+ 1, 1);
for (int i
= 1; i
<= size1
; ++i
) hash_a
[i
] = hash_a
[i
- 1] * 1331 + a
[i
- 1];
for (int i
= 1; i
<= size2
; ++i
) hash_b
[i
] = hash_b
[i
- 1] * 1331 + b
[i
- 1];
for (int i
= 1; i
<= size2
; ++i
) power
[i
] = power
[i
- 1] * 1331;
int left
= 1, right
= size2
, ans
= 0;
while (left
<= right
) {
int mid
= left
+ (right
- left
) / 2;
unordered_set
<unsigned int> set_a
;
for (int start
= 0; start
+ mid
- 1 < size1
; ++start
) {
unsigned int hash_val
= hash_a
[start
+ mid
] - hash_a
[start
] * power
[mid
];
set_a
.insert(hash_val
);
}
bool find
= false;
for (int start
= 0; start
+ mid
- 1 < size2
; ++start
) {
unsigned int hash_val
= hash_b
[start
+ mid
] - hash_b
[start
] * power
[mid
];
if (set_a
.count(hash_val
)) {
find
= true;
break;
}
}
if (find
) {
left
= mid
+ 1;
ans
= max(ans
, mid
);
} else {
right
= mid
- 1;
}
}
return ans
;
}
};
思考
没看懂范例，建议参考官方解答
