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.
1public class Solution {
2 public int FindLength(int[] nums1, int[] nums2) {
3 int maxLen = 0;
4 int[,] dp = new int[nums1.Length + 1, nums2.Length + 1];
5 for (int i = 1; i <= nums1.Length; i++) {
6 for (int j = 1; j <= nums2.Length; j++) {
7 if (nums1[i - 1] == nums2[j - 1]) {
8 dp[i, j] = dp[i - 1, j - 1] + 1;
9 maxLen = Math.Max(maxLen, dp[i, j]);
10 }
11 }
12 }
13 return maxLen;
14 }
15}The C# implementation leverages a 2D array for the DP table, updating the current length of matching subarrays, similar to the other language solutions.
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
The C solution selectively shifts and iterates over subarrays, checking integer matches directly as the two pointers overlap, recalculating lengths and ensuring a memory-efficient solution.