【LeetCode-每日一题】-718. 最长重复子数组

╰半夏微凉° 2023-02-22 05:17 1阅读 0赞

# 1. 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

# 2. 题目解析 #

1.  首先最先想到的应该是暴力，也就是直接跑3层循环，暴力解出ans的最大值
2.  其次，此题是一个动态规划，我们来看一张图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]  
    相当于我们求的是斜着的这一部分最多可以连续多长，此时动规的公式就比较明显了，  
    array\[i\]\[j\] = array\[i-1\]\[j-1\] + 1;
3.  最后是一种解法：滑动窗口，顾名思义，也就是通过保持A不变，滑动B，保持B不变，滑动A，最后取出其中最大的ans；  
    ![在这里插入图片描述][2020070122510822.gif_pic_center]

# 3. 题目代码 #

## 1. 动规 ##

public static int findLength1(int[] A, int[] B) {
        
    		int ans = 0;
    		int[][] array = new int[A.length + 1][B.length + 1];
    		for (int i = 1; i <= A.length; i++) {
        
    			for (int j = 1; j <= B.length; j++) {
        
    				if (A[i - 1] == B[j - 1]) {
        
    					array[i][j] = array[i - 1][j - 1] + 1;
    					ans = Math.max(ans, array[i][j]);
    				} else {
        
    					array[i][j] = 0;
    				}
    			}
    		}
    		return ans;
    	}

## 2. 滑动窗口代码 ##

public static int findLength(int[] A, int[] B) {
        
    		int ans = 0;
    		for (int i = 0; i < A.length; i++) {
        
    			int k = 0;
    			int len1 = i;
    			int len2 = 0;
    			while (len1 < A.length && len2 < B.length) {
        
    				if (A[len1] == B[len2]) {
        
    					k++;
    					len1++;
    					len2++;
    					ans = Math.max(ans, k);
    				} else {
        
    					k = 0;
    					len1++;
    					len2++;
    				}
    			}
    		}
    		for (int i = 0; i < B.length; i++) {
        
    			int k = 0;
    			int len1 = 0;
    			int len2 = i;
    			while (len1 < A.length && len2 < B.length) {
        
    				if (A[len1] == B[len2]) {
        
    					k++;
    					len1++;
    					len2++;
    					ans = Math.max(ans, k);
    				} else {
        
    					k = 0;
    					len1++;
    					len2++;
    				}
    			}
    		}
    		return ans;
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200701224140222.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200701224434824.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[2020070122510822.gif_pic_center]: https://img-blog.csdnimg.cn/2020070122510822.gif#pic_center