力扣718 最长重复子数组 java实现

718.最长重复子数组

给两个整数数组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

该题使用暴力解法明显时间复杂度较多，可以使用动态规划以空间换时间，定义动态规划数组dp[i][j] ：以下标i - 1为结尾的nums1，和以下标j - 1为结尾的nums2，最长重复子数组长度为dp[i][j]，两层循环遍历，若num1[i - 1] = nums2[j - 1] 则说明当前的nums1中的i - 1的位置和j - 1相同，在两者之前的长度上加一即可，例如nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]，i = 2,j = 2时， nums1[1] = nums[1] 在动态规划数组中说明在当前nums1的下标1位置和nums2的下标1相同，最长子序列只需在nums1的下标0和nums2的下表0的位置处的最长子数组加一即可，即dp[i][j] = dp[i - 1][j - 1] + 1

public static void main(String[] args) { // 测试用 int[] nums1 = {1,2,3,2,1}; int[] nums2 = {3,2,1,4,7}; System.out.println(findLength(nums1, nums2)); } public static int findLength(int[] nums1, int[] nums2) { int[][] dp = new int[nums1.length + 1][nums2.length + 1]; int res = 0; for (int i = 1; i <= nums1.length; i++) { for (int j = 1; j <= nums2.length; j++) { if (nums1[i - 1] == nums2[j - 1]){ dp[i][j] = dp[i - 1][j - 1] + 1; } res = Math.max(res, dp[i][j]); } } return res; }

以上为记录分享用，代码较差请见谅