Skip to content

Latest commit

 

History

History
105 lines (79 loc) · 3.22 KB

718. Maximum Length of Repeated Subarray.md

File metadata and controls

105 lines (79 loc) · 3.22 KB
Raw

718. Maximum Length of Repeated Subarray

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

注意，这道题和1143. Longest Common Subsequence要区分开，这道题是subarray即连续区间，LCS题为子序列，可以不连续。

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

思路

  • DP - 见代码1
  • 字符串哈希算法 - 见代码2

代码1

  • dp[i][j]数组表示 A[i...n] 和 B[j...m] 的最长公共连续subarray的元素个数(n, m为A, B长度)。
class Solution(object):
    def findLength(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        ans, n1, n2 = 0, len(A), len(B)
        dp = [(n2 + 1) * [0] for _ in range(n1 + 1)]
        for i in range(n1-1, -1, -1):
            for j in range(n2-1, -1, -1):
                if A[i] == B[j]:
                    dp[i][j] = 1 + dp[i+1][j+1]
                    if dp[i][j] > ans:
                        ans = dp[i][j]
        
        return ans

区别

对比我写的两道题的代码，区别在于处理subsequence时，当两个字符/数字不相同时，DP数组也是可以取值的，即dp[i][j] = max(dp[i+1][j], dp[i][j+1])， 表示当前位置的LCS数量，为字符串s1[i+1~]与s2[j~] or s1[i~]与s2[j+1~]的LCS最大值。

但是，如果是处理subarray，因为我们要求该位置的字符/数字必须与后一位相同，也就是要连续，假如A[i] != B[j]，那么dp[i][j] = 0，表示当把A[i], B[j]考虑在内，A[in] 与 B[jm] (包含i, j位)是没有共同的连续子区间。

代码2

  • 思路：字符串哈希算法。先对每个区间对应成n个数，转化为P进制，存到HashSet。这样匹配某一段区间时就是O(1)的复杂度。
class Solution {
    static long[] ha, hb, p;
    static int P = 131;
    static int n, m;
    
    static long get(long[] h, int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    
    public int findLength(int[] A, int[] B) {
        n = A.length; m = B.length;
        ha = new long[n + 1];
        hb = new long[m + 1];
        p = new long[n + 1];
        for (int i = 1; i <= n; i++) ha[i] = ha[i - 1] * P + A[i - 1];
        for (int i = 1; i <= m; i++) hb[i] = hb[i - 1] * P + B[i - 1];
        p[0] = 1;
        for (int i = 1; i <= n; i++) p[i] = p[i - 1] * P;
        
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }
    
    public boolean check(int mid) {
        Set<Long> S = new HashSet<>();
        for (int i = mid; i <= n; i++) S.add(get(ha, i - mid + 1, i));
        for (int i = mid; i <= n; i++) 
            if (S.contains(get(hb, i - mid + 1, i)))
                return true;
        return false;
    }
}