跳转至

718. 最长重复子数组

力扣链接(中等)：https://leetcode.cn/problems/maximum-length-of-repeated-subarray

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

示例 1：

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

示例 2：

Text Only
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

个人题解

C++
 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
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        const int N = 1010;
        int dp[N][N] = {};
        int result = 0;

        // 初始化
        // nums1 长度为 1 时
        for(int i = 0; i < nums2.size(); i++) {
            if(nums1[0] == nums2[i]) {
                dp[0][i] = 1; 
                result = dp[0][i];
            }
        }
        // nums2 长度为 1 时
        for(int i = 0; i < nums1.size(); i++) {
            if(nums1[i] == nums2[0]) {
                dp[i][0] = 1;
                result = dp[i][0];
            }
        }

        for(int i = 1; i < nums1.size(); i++) {
            for(int j = 1; j < nums2.size(); j++) {
                if(nums1[i] == nums2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
                result = max(result, dp[i][j]);
            }
        }

        // dp 调试用
        // for(int i = 0; i < nums1.size(); i ++){
        //     for(int j = 0; j < nums2.size(); j++) cout << dp[i][j] << ' ';
        //     cout << endl;
        // }

        return result;
    } 
};