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).
1#include <algorithm>
#include <unordered_map>
using namespace std;
int findLength(vector<int>& nums1, vector<int>& nums2) {
int maxLen = 0;
for (int offset = -nums2.size(); offset < nums1.size(); ++offset) {
int len = 0;
for (int i1Start = max(0, offset), i2Idx = max(0, -offset);
i1Start < nums1.size() && i2Idx < nums2.size();
++i1Start, ++i2Idx) {
if (nums1[i1Start] == nums2[i2Idx]) {
len++;
maxLen = max(maxLen, len);
} else {
len = 0;
}
}
}
return maxLen;
}C++ uses two offset arrays, checking elements and recording cumulative matching segments to straightforwardly identify overlaps and calculate maximum contiguous subarray lengths.