【LeeCode】718. 最长重复子数组

【题目描述】

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

​​​https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/​​

【示例】

【代码】

【代码】admin

通过率:  16/53

思路：暴力PO解， 2个for循环， 如果匹配到相等, 则开始依次遍历后面的 （如果遇到2个相同的数组，则直接返回）

package com.company;

import javax.swing.plaf.IconUIResource;
import java.util.*;

// 2022-02-18
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len = nums1.length;
        int len2 = nums2.length;
        int[] min;
        int[] max;
        if (len == len2) {
            min = nums1;
            max = nums2;
        }else{
            min = len < len2 ? nums1 : nums2;
            max = len < len2 ? nums2 : nums1;
        }
        int res = 0;

        for (int i = 0; i < min.length; i++){
            int count = 0;
            for (int j = 0; j < max.length; j++){
                if (min[i] == max[j]){
                    int left = i;
                    int right = j;
                    while (left < min.length && right < max.length){
                        if (min[left] == max[right]){
                            count++;
                            left++;
                            right++;
                        }else{
                            break;
                        }
                    }
                    if (res == len && len == len2) return len;
                    res = Math.max(count, res);
                }
            }
        }
        System.out.println(res);
        return res;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().findLength(new int[]{1,2,3,2,1}, new int[]{3,2,1,4,7}); // 输出: 3
        new Solution().findLength(new int[]{0,0,0,0,0}, new int[]{0,0,0,0,0}); // 输出: 5
    }
}

【代码】admin2

用例100%通过；

思路: 在第一版基础上，参考​​官网的暴PO思路​​ ( 引入第3个变量k, 如果 nums1[i + k] == nums2[j + k] 则count++)

package com.company;
import java.util.*;

// 2022-02-18
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res = 0;

        for(int i = 0; i < nums1.length; i++){
            for (int j = 0; j < nums2.length; j++){
                int k  = 0;
                // i+k 和 j+k是为了控制循环不越界
                while (i + k < nums1.length && j + k < nums2.length && nums1[i + k] == nums2[j + k]){
                    k++;
                }
                res = Math.max(res, k);
            }
        }
        System.out.println(res);
        return res;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().findLength(new int[]{1,2,3,2,1}, new int[]{3,2,1,4,7}); // 输出: 3
        new Solution().findLength(new int[]{0,0,0,0,0}, new int[]{0,0,0,0,0}); // 输出: 5
    }
}

【代码】​​动态规划​​

package com.company;
import java.util.*;

// 2022-02-18
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res = 0;
        int len = nums1.length;
        int len2 = nums2.length;
        // 如果最后一个元素相同, 则有至少一个公共元素 所以数组长度+1
        int[][] dp = new int[len+1][len2+1];
        // 如果 2个数组的第一个数字相同, 则数组中第二个数字的公共前缀+1
        // nums1[i] == nums2[j] ? 则
        for (int i = len - 1; i >= 0; i--){
            for (int j = len2 - 1; j >= 0; j--){
                dp[i][j] = nums1[i] == nums2[j] ? dp[i + 1][j + 1] + 1 : 0;
                res = Math.max(res, dp[i][j]);
            }
        }
        System.out.println(res);
        return res;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().findLength(new int[]{1,2,3,2,1}, new int[]{3,2,1,4,7}); // 输出: 3
        new Solution().findLength(new int[]{0,0,0,0,0}, new int[]{0,0,0,0,0}); // 输出: 5
    }
}