题目描述

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

样例

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

输入：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

算法

(动态规划) $O(n^2)$

1. 设 $f(i, j)$ 表示以 A[i] 和 B[j] 结尾的最长公共子数组的长度，有效下标从 1 开始。
2. 初始化 $f(i, 0) = 0, f(0, j) = 0$，其余待定。
3. 转移时，如果 A 数组的第 $i$ 个字符等于 B 数字的第 $j$ 个字符，则转移 $f(i, j) = f(i - 1, j - 1) + 1$；否则转移 $f(i, j) = 0$。
4. 最终答案为 $\max (f(i, j))$。
5. 可以通过转移顺序调整优化掉第一维的状态存储。

时间复杂度

• 状态数为 $O(nm)$，每次转移的时间复杂度为 $O(1)$，故总时间复杂度为 $O(nm)$。

空间复杂度

• 优化后，空间复杂度为 $O(m)$。

C++ 代码（空间优化前）

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        const int n = nums1.size(), m = nums2.size();

        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        int ans = 0;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else
                    f[i][j] = 0;

                ans = max(ans, f[i][j]);
            }

        return ans;
    }
};

C++ 代码（空间优化后）

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        const int n = nums1.size(), m = nums2.size();

        vector<int> f(m + 1, 0);
        int ans = 0;

        for (int i = 1; i <= n; i++)
            for (int j = m; j >= 1; j--) { // 注意转移顺序
                if (nums1[i - 1] == nums2[j - 1])
                    f[j] = f[j - 1] + 1;
                else
                    f[j] = 0;

                ans = max(ans, f[j]);
            }

        return ans;
    }
};