718. Maximum Length of Repeated Subarray 发表于 2021-12-17 DP1234567891011121314151617181920212223class Solution { public int findLength(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int maxLength = 0; // 定义 dp[i][j] 为以 nums1[i - 1] 结尾的子数组与以 nums2[j - 1] 结尾的子数组的最长公共子数组的长度 int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = 0; } maxLength = Math.max(maxLength, dp[i][j]); } } return maxLength; }} 因为 dp[i][j] 仅依赖 dp[i - 1][j - 1],所以可以降为一维数组: 1234567891011121314151617class Solution { public int findLength(int[] nums1, int[] nums2) { int[] dp = new int[nums2.length + 1]; // depends on dp[j - 1] int maxLength = 0; for (int i = 1; i <= nums1.length; i++) { for (int j = nums2.length; j >= 1; j--) { // 因为 dp[j] 依赖 dp[j - 1], 所以从右往左遍历 if (nums1[i - 1] == nums2[j - 1]) { dp[j] = dp[j - 1] + 1; } maxLength = Math.max(maxLength, dp[j]); } } return maxLength; }} Sliding Window12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152class Solution { public int findLength(int[] nums1, int[] nums2) { if (nums2.length < nums1.length) { return findLength(nums2, nums1); } // nums1: 3 4 5 // nums2: 5 6 7 8 9 int maxCommonLength = 0; // 3 4 5 3 4 5 // 5 6 7 8 9 -> 5 6 7 8 9 for (int i = nums1.length - 1; i >= 0; i--) { int j = 0; maxCommonLength = Math.max(maxCommonLength, getMaxCommonLength(nums1, i, nums2, j)); } // 3 4 5 3 4 5 // 5 6 7 8 9 -> 5 6 7 8 9 for (int j = 1; j <= nums2.length - nums1.length; j++) { int i = 0; maxCommonLength = Math.max(maxCommonLength, getMaxCommonLength(nums1, i, nums2, j)); } // 3 4 5 3 4 5 // 5 6 7 8 9 -> 5 6 7 8 9 for (int j = nums2.length - nums1.length + 1; j < nums2.length; j++) { int i = 0; maxCommonLength = Math.max(maxCommonLength, getMaxCommonLength(nums1, i, nums2, j)); } return maxCommonLength; } private int getMaxCommonLength(int[] nums1, int i, int[] nums2, int j) { int maxCommonLength = 0; int commonLength = 0; while (i < nums1.length && j < nums2.length) { if (nums1[i] == nums2[j]) { commonLength++; maxCommonLength = Math.max(maxCommonLength, commonLength); } else { commonLength = 0; } i++; j++; } return maxCommonLength; }} Reference718. Maximum Length of Repeated Subarray