LeetCode(中等)最长重复子数组(c#)

题目为 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

第一种解法，暴力算法，

时间复杂度N^3。此解法leetcode会超时。但逻辑没有问题，c#代码如下

public int FindLength(int[] A, int[] B) { int Maxlength = 0; for (int i = 0; i < A.Length; i++) { //List<int> pos = new List<int>(); //int[] posRes = B.TakeWhile((num, index) => num == 3).ToArray(); for (int j = 0; j < B.Length; j++) { if (A[i] == B[j]) { int a = i; int b = j; int tempLength = 1; while (a < A.Length-1&& b < B.Length-1&& A[++a] == B[++b]) { tempLength++; } if (tempLength>Maxlength) { Maxlength = tempLength; } } } } return Maxlength; }

第二种，动态规划

这个解法我没有想到，我考虑了双指针或者滑动模块。动态规划参考的是精选题解。可以看下这个题解的图片。精选题解 代码如下。

public int FindLength(int[] A, int[] B) { int Maxlength = 0; int[][] resCount = new int[A.Length + 1][]; for (int i = 0; i < resCount.Length; i++) { resCount[i] = new int[B.Length + 1]; } for (int i = A.Length-1; i >=0 ; i--) { for (int j = A.Length - 1; j >= 0; j--) { if (A[i] == B[j]) { int tempMax = resCount[i + 1][j + 1] + 1; resCount[i][j] = tempMax; Maxlength = tempMax > Maxlength ? tempMax : Maxlength; } } } return Maxlength; }

第三种、滑动模块

滑动模块参考精选题解这个兄弟的说明一看就懂，链接如下 理解了滑动模块的思路后，我的代码是将两个数组a和b对齐，先将A固定，向左移动B。然后是B固定，向左移动A。 c#代码如下

public int findLengthHelper(int[] A, int[] B) { int aLen = A.Length; int bLen = B.Length; //比较的总共次数 int TotalCount = aLen + bLen - 1; int res = 0; // A固定，向左移动B for (int i = 0; i < bLen; i++) { int aSta = 0; int bSta = i; int Len = bLen - i > aLen ? aLen : bLen - i; int temp = maxLength(A, B, aSta, bSta, Len); res = temp > res ? temp : res; } // B固定，向左移动A for (int j = 0; j < aLen; j++) { int aSta = j; int bSta = 0; int Len = aLen - j > bLen ? bLen : aLen - j; int temp = maxLength(A, B, aSta, bSta, Len); res = temp > res ? temp : res; } return res; } /// <summary> /// 判断红框内的最大相同长度 /// </summary> /// <param name="A">数组A</param> /// <param name="B">数组B</param> /// <param name="aStart">A元素比较的开始位置</param> /// <param name="bStart">B元素比较的开始位置</param> /// <param name="len">比较的总长度</param> /// <returns></returns> public int maxLength(int[] A, int[] B, int aStart, int bStart, int len) { int maxLen = 0, count = 0; for (int i = 0; i < len; i++) { if (aStart + i < A.Length && bStart + i < B.Length && A[aStart + i] == B[bStart + i]) { count++; maxLen = maxLen > count ? maxLen : count; } else { count = 0; } } return maxLen; }