题目

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums1.length, nums2.length <= 1000

  • 0 <= nums1[i], nums2[i] <= 100

    解题方法

    动态规划

    设定动态数组dp[i][j]表示数组1截止到下标i-1处和数组2下标截止到j-1处对应的公共最长子数组的长度，记录dp数组最大值，递推公式如下：
    718. 最长重复子数组 - 图1
    为了进一步压缩空间复杂度，将该二维数组压缩为一维数组dp[j]。
    时间复杂度O(n1*n2)，空间复杂度O(n2)。
    C++代码：

    1. class Solution {
    2. public:
    3.   int findLength(vector<int>& nums1, vector<int>& nums2) {
    4.       int n1 = nums1.size();
    5.       int n2 = nums2.size();
    6.       vector<int> dp(n2+1, 0);
    7.       int result = 0;
    8.       for(int i=0; i<n1; i++) {
    9.           for(int j=n2; j>0; j--) {
    10.               dp[j] = nums1[i] == nums2[j-1] ? dp[j-1]+1 : 0;
    11.               result = result > dp[j] ? result : dp[j];
    12.           }
    13.       }
    14.       return result;
    15.   }
    16. };

    滑动窗口

    寻找最长重复子数组可以看做一个数组固定，另一个数组滑动，随后在重叠区域内求最长的重复子数组长度即可。
    时间复杂度O((m+n)*min(m+n))，空间复杂度O(1)。
    C++代码：

    class Solution {
public:
  int getmaxsub(vector<int>& nums1, vector<int>& nums2) {
      int n1 = nums1.size();
      int n2 = nums2.size();
      int result = 0;
      for(int i=0; i<n1; i++) {
          int len = min(n1-i, n2);
          int tmp = 0;
          for(int k=0; k<len; k++) {
              tmp = nums1[i+k]==nums2[k] ? ++tmp : 0;
              result = result > tmp ? result : tmp;
          }
      }
      return result;
  }

  int findLength(vector<int>& nums1, vector<int>& nums2) {
      int result1 = getmaxsub(nums1, nums2);
      int result2 = getmaxsub(nums2, nums1);
      return result1 > result2 ? result1 : result2;
  }
};