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.
1var findLength = function(nums1, nums2) {
2 let maxLen = 0;
3 const dp = Array(nums1.length + 1).fill(0).map(() => Array(nums2.length + 1).fill(0));
4 for (let i = 1; i <= nums1.length; i++) {
5 for (let j = 1; j <= nums2.length; j++) {
6 if (nums1[i - 1] === nums2[j - 1]) {
7 dp[i][j] = dp[i - 1][j - 1] + 1;
8 maxLen = Math.max(maxLen, dp[i][j]);
9 }
10 }
11 }
12 return maxLen;
13};JavaScript solution creates a DP table using arrays. By iterating and checking element equality, it manages subarray lengths just as in other implementations.
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 <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.