[LeetCode] 718. Maximum Length of Repeated Subarray #718

grandyang · 2019-05-30T16:25:45Z

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

**Input:**
A: [1,2,3,2,1]
B: [3,2,1,4,7]
**Output:** 3
**Explanation:** 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

这道题给了我们两个数组A和B，让返回连个数组的最长重复子数组。那么如果将数组换成字符串，实际这道题就是求 Longest Common Substring 的问题了，而貌似 LeetCode 上并没有这种明显的要求最长相同子串的题，注意需要跟最长子序列 Longest Common Subsequence 区分开，关于最长子序列会在 follow up 中讨论。好，先来看这道题，既然是子数组，那么重复的地方一定是连续的，而且起点可能会是在数组中的任意地方，这样的话，最暴力的方法就是遍历A中的每个位置，把每个位置都当作是起点进行和B从开头比较，每次A和B都同时前进一个，假如相等，则计数器会累加1，不相等的话，计数器会重置为0，每次用计数器 cnt 的长度来更新结果 res。然后用同样的方法对B也处理一遍，把每个位置都当作是起点进行和A从开头比较，每次A和B都同时前进一个，这样最终下来，就可以求出最长重复子数组的长度，令人惊喜的是，这种暴力搜索解法的击败率相当的高，参见代码如下：

解法一：

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size(), res = 0;
        for (int offset = 0; offset < m; ++offset) {
            for (int i = offset, j = 0; i < m && j < n;) {
                int cnt = 0;
                while (i < m && j < n && A[i++] == B[j++]) ++cnt;
                res = max(res, cnt);
            }
        }
        for (int offset = 0; offset < n; ++offset) {
            for (int i = 0, j = offset; i < m && j < n;) {
                int cnt = 0;
                while (i < m && j < n && A[i++] == B[j++]) ++cnt;
                res = max(res, cnt);
            }
        }
        return res;
    }
};

我们还可以使用二分法+哈希表来做，别问博主怎么知道（看了题目标签，然后去论坛上找对应的解法即可，哈哈～）。虽然解法看起来很炫，但不太简洁，不是博主的 style，但还是收录进来吧。这里使用二分搜索法来找什么呢？其实是来直接查找最长重叠子数组的长度的，因为这个长度是有范围限制的，在 [0, min(m, n)] 之间，其中m和n分别是数组A和B的长度。这样每次折半出一个 mid，然后验证有没有这么一个长度为 mid 的子数组在A和B中都存在。从数组中取子数组有些麻烦，可以将数组转为字符串，取子串就相对来说容易一些了。将数组A和B都先转化为字符串 strA 和 strB，但是这里很 tricky，转换的方式不能是直接将整型数字转为字符串，再连接起来，这样会出错，因为会导致一个整型数占据多位字符，所以这里是需要将每个整型数直接加入字符串，从而将该整型数当作 ASCII 码来处理，寻找对应的字符，使得转换后的 strA 和 strB 变成各种凌乱的怪异字符，不过不影响解题。这里的二分应该属于博主之前的总结贴 LeetCode Binary Search Summary 二分搜索法小结中的第四类，但是写法上却跟第三类的变形很像，因为博主平时的习惯是右边界设置为开区间，所以初始化为 min(m, n)+1，当然博主之前就说过二分搜索的写有各种各样的，像这个帖子中写法也是可以的。博主的这种写法实际上是在找第一个不大于目标值的数，这里的目标值就是那个 helper 子函数，也就是验证函数。如何实现这个验证函数呢，由于是要找长度为 len 的子串是否同时存在于 strA 和 strB 中，可以用一个 HashSet 保存 strA 中所有长度为 len 的子串，然后遍历 strB 中所有长度为 len 的子串，假如有任何一个在 HashSet 中存在，则直接返回 true，否则循环退出后，返回 false，参见代码如下：

解法二：

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        string strA = stringify(A), strB = stringify(B);
        int left = 0, right = min(A.size(), B.size()) + 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (helper(strA, strB, mid)) left = mid + 1;
            else right = mid;
        }
        return right - 1;
    }
    bool helper(string& strA, string& strB, int len) {
        unordered_set<string> st;
        for (int i = 0, j = len; j <= strA.size(); ++i, ++j) {
            st.insert(strA.substr(i, j - i));
        }
        for (int i = 0, j = len; j <= strB.size(); ++i, ++j) {
            if (st.count(strB.substr(i, j - i))) return true;  
        } 
        return false;
    }
    string stringify(vector<int>& nums) {
        string res;
        for (int num : nums) res += num;
        return res;
    }
};

对于这种求极值的问题，动态规划 Dynamic Programming 一直都是一个很好的选择，这里使用一个二维的 DP 数组，其中 dp[i][j] 表示数组A的前i个数字和数组B的前j个数字在尾部匹配的最长子数组的长度，如果 dp[i][j] 不为0，则A中第i个数组和B中第j个数字必须相等，且 dp[i][j] 的值就是往前推分别相等的个数，比对于这两个数组 [1,2,2] 和 [3,1,2]，dp 数组为：

注意观察，dp 值不为0的地方，都是当 A[i] == B[j] 的地方，而且还要加上左上方的 dp 值，即 dp[i-1][j-1]，所以当前的 dp[i][j] 就等于 dp[i-1][j-1] + 1，而一旦 A[i] != B[j] 时，直接赋值为0，不用多想，因为子数组是要连续的，一旦不匹配了，就不能再增加长度了。每次算出一个 dp 值，都要用来更新结果 res，这样就能得到最长相同子数组的长度了，参见代码如下：

解法三：

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int res = 0, m = A.size(), n = B.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = (A[i - 1] == B[j - 1]) ? dp[i - 1][j - 1] + 1 : 0;
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

Follow up：在开始时，博主提到了要跟最长相同子序列 Longest Common Subsequence 区分开来，虽然 LeetCode 没有直接求最大相同子序列的题，但有几道题利用到了求该问题的思想，比如 Delete Operation for Two Strings 和 Minimum ASCII Delete Sum for Two Strings 等，但现在 LeetCode 已经补上求 LCS 的题了，参见 Longest Common Subsequence :)

Github 同步地址：

#718

类似题目：

Minimum Size Subarray Sum

Longest Common Subsequence

参考资料：

https://leetcode.com/problems/maximum-length-of-repeated-subarray/

https://leetcode.com/problems/maximum-length-of-repeated-subarray/discuss/109068/JavaC%2B%2B-Clean-Code-8-lines

https://leetcode.com/problems/maximum-length-of-repeated-subarray/discuss/109039/Concise-Java-DP%3A-Same-idea-of-Longest-Common-Substring

https://leetcode.com/problems/maximum-length-of-repeated-subarray/discuss/109033/Solution-1%3A-DP-O(n2)-with-O(n)-space-Solution-2%3A-Stringify

LeetCode All in One 题目讲解汇总(持续更新中...)

The text was updated successfully, but these errors were encountered: