leetcode 链接：718. 最长重复子数组

题目

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

示例：

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

解答 & 代码

动态规划：

• 设置动态规划数组 dp，dp[i][j] 代表分别以 nums1[i] 结尾、以 nums2[j] 结尾的公共子数组长度
• 状态转移方程：

• 初始化：

  • 若 i 为 0，即 nums1 只有 1 个字符，那么当 nums[0] == nums[j] 时，nums[0][j] = 1，否则 nums[0][j] = 0

  • 若 j 为 0，即 nums2 只有 1 个字符，那么当 nums[i] == nums[0] 时，nums[i][0] = 1，否则 nums[i][0] = 0

    class Solution {
    public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
       int size1 = nums1.size();
       int size2 = nums2.size();
       if(size1 == 0 || size2 == 0)
           return 0;
    
       int maxLen = 0;
       vector<vector<int>> dp(size1, vector<int>(size2, 0));
       for(int i = 0; i < size2; ++i)
       {
           dp[0][i] = nums1[0] == nums2[i] ? 1 : 0;
           maxLen = max(maxLen, dp[0][i]);
       }            
       for(int i = 1; i < size1; ++i)
       {
           dp[i][0] = nums1[i] == nums2[0] ? 1 : 0;
           maxLen = max(maxLen, dp[i][0]);
       }
    
       for(int i = 1; i < size1; ++i)
       {
           for(int j = 1; j < size2; ++j)
           {
               if(nums1[i] == nums2[j])
               {
                   dp[i][j] = dp[i - 1][j - 1] + 1;
                   maxLen = max(maxLen, dp[i][j]);
               }
           }
       }
       return maxLen;
    }
    };
    

    执行结果： ``` 执行结果：通过

执行用时：260 ms, 在所有 C++ 提交中击败了 76.00% 的用户 内存消耗：106.2 MB, 在所有 C++ 提交中击败了 68.73% 的用户 ```