718. Maximum Length of Repeated Subarray

 

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个数字必须相等,比对于这两个数组 [1,2,2] 和 [3,1,2],dp 数组为:

 

  3 1 2
1 0 1 0
2 0 0 2
2 0 0 1

 

注意观察,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 等,详细讨论请参见评论区一楼 :)

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/718

 

类似题目:

Minimum Size Subarray Sum

 

参考资料:

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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation