leetcode-cn Daily Challenge on July 1st, 2020
Difficulty : Medium
Given two integer arrays
A
andB
, return the maximum length of an subarray that appears in both arrays.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].
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
- mine
- Java
-
DP
Runtime: 96 ms, faster than 26.05%, Memory Usage: 99.3 MB, less than 5.89% of Java online submissions
// O(S)time O(S)space // S = lenA * lenB public int findLength(int[] A, int[] B) { int lenA = A.length, lenB = B.length; int dp[][] = new int[lenA + 1][lenB + 1]; int res = 0; for(int i = 1; i <= lenA; i++){ for(int j = 1; j <= lenB; j++){ if( A[i - 1] == B[j - 1]){ dp[i][j] = dp[i-1][j-1] + 1; } res = Math.max(res, dp[i][j]); } } return res; }
-
DP space optimization
Runtime: 82 ms, faster than 30.32%, Memory Usage: 39.3 MB, less than 90.41% of Java online submissions
// O(lenA * lenB)time // O(min(lenA, lenB))space public int findLength(int[] A, int[] B) { if(A.length < B.length){ int[] t = A; A = B; B = t; } int res = 0; int[][] dp = new int[2][B.length + 1]; for(int i = 1; i <= A.length; i++){ for(int j = 1; j <= B.length; j++){ dp[i & 1][j] = A[i - 1] == B[j - 1] ? dp[(i - 1) & 1][j - 1] + 1 : 0; res = Math.max(res, dp[i & 1][j]); } } return res; }
-
- Java
- leetcode solution
-
Sliding Window
Runtime: 58 ms, faster than 42.19%, Memory Usage: 38.7 MB, less than 99.78% of Java online submissions
// O((lenA + lenB) * min(lenA,lenB))time // O(1)space public int findLength(int[] A, int[] B) { int n = A.length, m = B.length; int ret = 0; for (int i = 0; i < n; i++) { int len = Math.min(m, n - i); int maxlen = maxLength(A, B, i, 0, len); ret = Math.max(ret, maxlen); } for (int i = 0; i < m; i++) { int len = Math.min(n, m - i); int maxlen = maxLength(A, B, 0, i, len); ret = Math.max(ret, maxlen); } return ret; } public int maxLength(int[] A, int[] B, int addA, int addB, int len) { int ret = 0, k = 0; for (int i = 0; i < len; i++) { if (A[addA + i] == B[addB + i]) { k++; } else { k = 0; } ret = Math.max(ret, k); } return ret; }
-
BinarySerach & Hash
Runtime: 26 ms, faster than 98.96%, Memory Usage: 49.4 MB, less than 16.13% of Java online submissions
//O(S)time O(lenA)space //S = (lenA + lenB) * log(min(lenA, LenB)) int mod = 1000000009; int base = 113; public int findLength(int[] A, int[] B) { int left = 1, right = Math.min(A.length, B.length) + 1; while (left < right) { int mid = (left + right) >> 1; if (check(A, B, mid)) { left = mid + 1; } else { right = mid; } } return left - 1; } public boolean check(int[] A, int[] B, int len) { long hashA = 0; for (int i = 0; i < len; i++) { hashA = (hashA * base + A[i]) % mod; } Set<Long> bucketA = new HashSet<Long>(); bucketA.add(hashA); long mult = qPow(base, len - 1); for (int i = len; i < A.length; i++) { hashA = ((hashA - A[i - len] * mult % mod + mod) % mod * base + A[i]) % mod; bucketA.add(hashA); } long hashB = 0; for (int i = 0; i < len; i++) { hashB = (hashB * base + B[i]) % mod; } if (bucketA.contains(hashB)) { return true; } for (int i = len; i < B.length; i++) { hashB = ((hashB - B[i - len] * mult % mod + mod) % mod * base + B[i]) % mod; if (bucketA.contains(hashB)) { return true; } } return false; } // Rabin-Karp public long qPow(long x, long n) { long ret = 1; while (n != 0) { if ((n & 1) != 0) { ret = ret * x % mod; } x = x * x % mod; n >>= 1; } return ret; }
-