718. 最长重复子数组(中等)

Posted on In Views:

1，问题描述

718. 最长重复子数组

难度：中等

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

1
2
3
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

1
2
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100

2，初步思考

​ 模式识别：本质就是子问题，直接想到了自上而下的递归，以及自下而上的动态规划

​ 构造状态转移方程

​ dp【i】【j】=nums【i】==nums2【j】? (dp【i-1】【j-1】+1):0

0,0,0,0,0 与 0,0,0,0,0

0 0 0 0 0
0 1 1 1 1 1
0 1 2 2 2 2
0 1 2 3 3 3
0 1 2 3 4 5
0 1 2 3 4 5

3,2,1,4,7 与 1,2,3,2,1

3 2 1 4 7
1 0 0 1 0 0
2 0 1 0 0 0
3 1 0 1 0 0
2 0 2 0 1 0
1 0 0 3 0 1

1,0,1,0,1 与 0,1,1,1,1

1 0 1 0 1
0 0 1 0 1 0
1 1 0 2 0 2
1 1 0 1 0 1
1 1 0 1 0 1
1 1 0 1 0 1

2,3,4,1 与 1,2,3,4,5

2 3 4 1
1 0 0 0 1
2 1 0 0 0
3 0 2 0 0
4 0 0 3 0
5 0 0 0 0

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class _718最长重复子数组 {

    // 解法4:二分查找+hash(有点麻烦，待)
    public int findLength_binary_search(int[] nums1, int[] nums2) {
        int max = 0;
        return max;
    }

    // 解法3:滑动窗口，时间复杂度O(n^2)，空间复杂度O(1)
    public int findLength_slide_window(int[] nums1, int[] nums2) {
        int max = 0;
        int len1 = nums1.length,len2 = nums2.length;
        for (int i = 0; i < len1; i++) {
            max = Math.max(max, maxLength(nums1, nums2, i, 0));
        }
        for (int i = 0; i < len2; i++) {
            max = Math.max(max, maxLength(nums1, nums2, 0, i));
        }
        return max;
    }

    private int maxLength(int[] nums1, int[] nums2, int i1, int i2){
        int max = 0;
        int counter = Math.min(nums1.length-i1, nums2.length-i2);
        int temp = 0;
        for (int i = 0; i < counter; i++) {
            if(nums1[i1+i] == nums2[i2+i]){
                temp++;
            }else {
                temp = 0;
            }
            max = Math.max(max, temp);
        }
        return max;
    }

    // 解法2:暴力破解，遍历3次时间复杂度O(n^3)，运行超时
    public int findLength_brute_force(int[] nums1, int[] nums2) {
        int max = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int n1 = i;
                int n2 = j;
                if(nums1[n1] == nums2[j]){
                    while (n1 < nums1.length && n2 < nums2.length && nums1[n1] == nums2[n2]){
                        n1++;
                        n2++;
                        max = Math.max(max, n1-i);
                    }
                }
            }
        }
        return max;
    }

    // 解法1:动态规划
    // 模式识别：本质就是子问题，直接想到了自上而下的递归，以及自下而上的动态规划
    public int findLength(int[] nums1, int[] nums2) {
        // 初始化dp
        int max = 0;
        int[][] dp = new int[nums1.length][nums2.length];
        for (int i = 0; i < nums1.length; i++) {
            dp[i][0] = nums1[i]==nums2[0]?1:0;
            max = Math.max(max, dp[i][0]);
        }
        for (int i = 0; i < nums2.length; i++) {
            dp[0][i] = nums1[0]==nums2[i]?1:0;
            max = Math.max(max, dp[0][i]);
        }

        // 处理dp数据
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 1; j < nums2.length; j++) {
                int temp = nums1[i]==nums2[j]?1:0;
                dp[i][j] = temp*(dp[i-1][j-1]+temp);
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        _718最长重复子数组 longestRepeatingSubarray = new _718最长重复子数组();
//        System.out.println(longestRepeatingSubarray.findLength(new int[]{1,2,3,2,1}, new int[]{3,2,1,4,7}));
//        System.out.println(longestRepeatingSubarray.findLength(new int[]{0,0,0,0,0}, new int[]{0,0,0,0,0}));
//        System.out.println(longestRepeatingSubarray.findLength(new int[]{0,0,0,0,1}, new int[]{1,0,0,0,0}));
        System.out.println(longestRepeatingSubarray.findLength_slide_window(new int[]{0,1,1,1,1}, new int[]{1,0,1,0,1}));
    }
}
/**
 * 1,2,3,2,1
 * 3,2,1,4,7
 */

​ 方法三：二分查找 + 哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    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;
    }
    
    // 使用快速幂计算 x^n % mod 的值
    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;
    }
}

4，思考过程

​ 解法不难，但是方法三：二分查找 + 哈希的解法还没来得及弄懂