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 <vector>
2#include <algorithm>
3
4using namespace std;
5
6int findLength(vector<int>& nums1, vector<int>& nums2) {
7 int maxLen = 0;
8 vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
9 for (int i = 1; i <= nums1.size(); i++) {
10 for (int j = 1; j <= nums2.size(); j++) {
11 if (nums1[i - 1] == nums2[j - 1]) {
12 dp[i][j] = dp[i - 1][j - 1] + 1;
13 maxLen = max(maxLen, dp[i][j]);
14 }
15 }
16 }
17 return maxLen;
18}This C++ implementation uses a vector of vectors for the DP table. Similar logic is applied to update the table and track the maximum length as in the C solution.
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 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.