Sponsored
Sponsored
This approach uses a 2D DP array where dp[i][j] represents the length of the longest common subarray ending at nums1[i-1] and nums2[j-1]. Initialize the DP table with zeros. If nums1[i-1] == nums2[j-1], set dp[i][j] = dp[i-1][j-1] + 1, otherwise set it to 0. Track the maximum length found throughout the process.
Time Complexity: O(n * m), where n and m are the lengths of nums1 and nums2, respectively. Space Complexity: O(n * m) due to the DP table.
1#include <stdio.h>
2#include <string.h>
3
4int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {
5 int dp[nums1Size + 1][nums2Size + 1];
6 memset(dp, 0, sizeof(dp));
7 int maxLen = 0;
8 for (int i = 1; i <= nums1Size; i++) {
9 for (int j = 1; j <= nums2Size; j++) {
10 if (nums1[i - 1] == nums2[j - 1]) {
11 dp[i][j] = dp[i - 1][j - 1] + 1;
12 if (dp[i][j] > maxLen) maxLen = dp[i][j];
13 }
14 }
15 }
16 return maxLen;
17}This solution constructs a 2D array for maintaining the lengths of common subarrays at each ending position for both arrays. When matching elements are found, it extends the length from the previous subarray and potentially updates the maximum length found.
This approach involves using a sliding window over the two arrays with the help of a hashing method to check potential matches of subarrays. By varying the window size, you can find the length of the longest matching subarray without needing a full DP table.
Time Complexity: O(n * m), Space Complexity: O(1).
1public class Solution {
public int FindLength(int[] nums1, int[] nums2) {
int maxLen = 0;
for (int k = 0; k < nums1.Length; k++) {
int len = 0;
for (int i = k, j = 0; i < nums1.Length && j < nums2.Length; i++, j++) {
if (nums1[i] == nums2[j]) {
len++;
maxLen = Math.Max(maxLen, len);
} else {
len = 0;
}
}
}
for (int k = 0; k < nums2.Length; k++) {
int len = 0;
for (int i = 0, j = k; i < nums1.Length && j < nums2.Length; i++, j++) {
if (nums1[i] == nums2[j]) {
len++;
maxLen = Math.Max(maxLen, len);
} else {
len = 0;
}
}
}
return maxLen;
}
}By initializing two sliding match-checks, one per offset array, the C# solution ensures overlap is tracked with max len updates and handled directly via looping conditions.