初级算入门_最长重复子数组

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

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,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

代码:

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1=nums1.length,len2=nums2.length;
        int[][] table = new int[len1+1][len2+1];
        //初始化table行列
        /*
        for(int i=0;i<len1;i++){
            if(nums1[i]==nums2[0]){
                table[i][0]=1;
            }
        }
        for(int i=0;i<len2;i++){
            if(nums1[0]==nums2[i]){
                table[0][i]=1;
            }
        }
        */
        //往里面填入数字+1计算长度（对角+1）
        int res =0;
        for(int i=0; i<len1 ; i++){
            for(int j=0; j<len2 ; j++){
                if( nums1[i] == nums2[j] ){
                    //如果相等,就把上次的值+1  （上次值就是对角md）
                    table[i+1][j+1]=table[i][j]+1;
                    res=Math.max(res,table[i+1][j+1]);
                }else{
                    table[i+1][j+1]=0;
                }  
            }        
        }
        return res;
    }
}

思路:

按理说很好容易的一个题,给我凎蒙了

我以为是数组找同一个元素,仔细读题之后并不是这样。寻找最长的公共子数组的长度。这是很关键的一点。以示例1为例子，他们都有的子数组是321和21和1，当然了相同元素也算是一个数组，但是我们需要找的是一个子数组，还是最长的，前提条件就是存在相同元素并且这相同元素在两个数组里面是挨着的。

那[0,0,0,0,1]和[1,0,0,0,0]举例子

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

以示例1画表

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

上面我们可以看出来当第二个连续数出现时候，下标就开始改变，我们从for循环可以知道外for一次内for一轮。所以赋值出现了下面的这种情况,还有一点的是因为你是从上次的i和j开始找的，所以下次的i和j都加1后是下角的值，也就是说，我上次再[1,1]单元格相等赋值为1之后，那么再若在[2,2]单元格相等的话我们需要+1当前值就是2以此类推，要是不明白的话，你可以理解就是找对角线+1。

我们就可以从初始化数组从0开始for

 for(int i=0; i<len1 ; i++){
            for(int j=0; j<len2 ; j++){
                if( nums1[i] == nums2[j] ){
                    //如果相等,就把上次的值+1
                    table[i+1][j+1]=table[i][j]+1;
                    //进行比较，看看谁最大res是记录最大值
                    res=Math.max(res,table[i+1][j+1]);
                }else{
                    table[i+1][j+1]=0;
                }  
            }        
}

至于为什么这样写，不把二维数组初始值赋值为num1和num2的length，那是因为测试用例的时候有一个值相等的数组过不去

也就是nums1 =[1,2,3,2,8]和nums2 =[5,6,1,4,7]

这里面只有1是相等的，还算是一个数组。。。。。要是再外面判断二维数组里面的最大值，这样的时间复杂度就太高了。。。

所以只能再二维数组+1了，所以上面图表的显示方式应该是整体往右下角整体移动一下，剩下位置补0。

整体核心在这里

递推：

if(A[i]==B[j]){
        dp[i][j]=dp[i-1][j-1]+1;
    }else{
        dp[i][j]=0;
}