Question

718. Maximum Length of Repeated Subarray

中文文档

Description

Given two integer arrays nums1 and nums2, return _the maximum length of a subarray that appears in both arrays_.

 

Example 1:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5
Explanation: The repeated subarray with maximum length is [0,0,0,0,0].

 

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

Solutions

Solution 1

class Solution:
  def findLength(self, nums1: List[int], nums2: List[int]) -> int:
    m, n = len(nums1), len(nums2)
    f = [[0] * (n + 1) for _ in range(m + 1)]
    ans = 0
    for i in range(1, m + 1):
      for j in range(1, n + 1):
        if nums1[i - 1] == nums2[j - 1]:
          f[i][j] = f[i - 1][j - 1] + 1
          ans = max(ans, f[i][j])
    return ans

class Solution {
  public int findLength(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    int[][] f = new int[m + 1][n + 1];
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (nums1[i - 1] == nums2[j - 1]) {
          f[i][j] = f[i - 1][j - 1] + 1;
          ans = Math.max(ans, f[i][j]);
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int findLength(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    vector<vector<int>> f(m + 1, vector<int>(n + 1));
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (nums1[i - 1] == nums2[j - 1]) {
          f[i][j] = f[i - 1][j - 1] + 1;
          ans = max(ans, f[i][j]);
        }
      }
    }
    return ans;
  }
};

func findLength(nums1 []int, nums2 []int) (ans int) {
  m, n := len(nums1), len(nums2)
  f := make([][]int, m+1)
  for i := range f {
    f[i] = make([]int, n+1)
  }
  for i := 1; i <= m; i++ {
    for j := 1; j <= n; j++ {
      if nums1[i-1] == nums2[j-1] {
        f[i][j] = f[i-1][j-1] + 1
        if ans < f[i][j] {
          ans = f[i][j]
        }
      }
    }
  }
  return ans
}

function findLength(nums1: number[], nums2: number[]): number {
  const m = nums1.length;
  const n = nums2.length;
  const f = Array.from({ length: m + 1 }, _ => new Array(n + 1).fill(0));
  let ans = 0;
  for (let i = 1; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      if (nums1[i - 1] == nums2[j - 1]) {
        f[i][j] = f[i - 1][j - 1] + 1;
        ans = Math.max(ans, f[i][j]);
      }
    }
  }
  return ans;
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function (nums1, nums2) {
  const m = nums1.length;
  const n = nums2.length;
  const f = Array.from({ length: m + 1 }, _ => new Array(n + 1).fill(0));
  let ans = 0;
  for (let i = 1; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      if (nums1[i - 1] == nums2[j - 1]) {
        f[i][j] = f[i - 1][j - 1] + 1;
        ans = Math.max(ans, f[i][j]);
      }
    }
  }
  return ans;
};