[Swift]LeetCode718. 最长重复子数组 | Maximum Length of Repea

发布时间：2020-12-14 05:02:38 所属栏目：百科来源：网络整理

导读：Given two integer arrays? A ?and? B ,return the maximum length of an subarray that appears in both arrays. Example 1: Input:A: [1,2,3,1]B: [3,1,4,7]Output: 3Explanation: The repeated subarray with maximum length is [3,1].? Note: 1 = len(A)

Given two integer arrays?A?and?B,return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,1]
B: [3,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3,1].?

Note:

1 <= len(A),len(B) <= 1000
0 <= A[i],B[i] < 100

给两个整数数组?A?和?B?，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入:
A: [1,7]
输出: 3
解释: 
长度最长的公共子数组是 [3,1]。

说明:

1 <= len(A),B[i] < 100

308ms

 1 class Solution {
 2     func findLength(_ A: [Int],_ B: [Int]) -> Int {
 3         var ret = 0
 4         let lenA = A.count,lenB = B.count
 5         for k in 1..<(lenA + lenB) {
 6             var i = max(0,lenA - k)
 7             var j = max(0,k - lenA)
 8             var len = 0
 9             while i < lenA && j < lenB {
10                 len = (A[i] == B[j]) ? (len + 1) : 0
11                 ret = max(ret,len)
12                 i += 1
13                 j += 1
14             }
15         }
16         return ret
17     }
18 }

1304ms

 1 class Solution {
 2     func findLength(_ A: [Int],_ B: [Int]) -> Int {
 3         let m = A.count,n = B.count
 4         var res = 0
 5         
 6         var dp = [[Int]](repeating:[Int](repeating: 0,count: n+1),count: m + 1)
 7         
 8         for i in 1...m {
 9             for j in 1...n {
10                 if A[i-1] == B[j-1] {
11                     dp[i][j] = 1 + dp[i-1][j-1]
12                     res = max(res,dp[i][j])
13                 }
14             }
15         }
16         return res
17     }
18 }

Runtime:?2028 ms

Memory Usage:?25.4 MB

 1 class Solution {
 2     func findLength(_ A: [Int],_ B: [Int]) -> Int {
 3         var res:Int = 0
 4         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:B.count + 1),count:A.count + 1)
 5         for i in 1..<dp.count
 6         {
 7             for j in 1..<dp[i].count
 8             {
 9                 dp[i][j] = (A[i - 1] == B[j - 1]) ? dp[i - 1][j - 1] + 1 : 0
10                 res = max(res,dp[i][j])
11             }
12         }
13         return res
14     }
15 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!