最长公共子串(最长重复子数组)

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

---

暴力解法

这种解法过于粗暴，无法通过OJ

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                k = 0
                while i+k < len(nums1) and j+k < len(nums2) and nums1[i+k] == nums2[j+k]:
                    k += 1
                ans = max(ans, k)
        return ans

不太优雅的滑动窗口？

分别使用A数组的每一个数为起点与B数组比较，如果数字相同计数加1
然后交换A B重新比较

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        ans = 0
        j = 0
        
        for offset in range(m):
            i = offset
            j = 0
            while i < m and j < n:
                count = 0
                while i < m and j < n and nums1[i] == nums2[j]:
                    count += 1
                    i += 1
                    j += 1
                j += 1
                i += 1
                ans = max(ans, count)
        
        for offset in range(n):
            j = offset
            i = 0
            while i < m and j < n:
                count = 0
                # print('i, j, count', i, j, count)
                while i < m and j < n and nums1[i] == nums2[j]:
                    count += 1
                    i += 1
                    j += 1
                j += 1
                i += 1
                ans = max(ans, count)
        
        return ans

滑动窗口

假设已经对齐了两个数组的起点，我们就可以对两个数组进行一趟遍历，求得最长的数组

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        def helper(start1, start2, length):
            k = 0
            ans = 0
            for i in range(length):
                if nums1[start1+i] == nums2[start2+i]:
                    k += 1
                else:
                    k = 0
                ans = max(ans, k)
            return ans

        m = len(nums1)
        n = len(nums2)
        ans = 0
        for i in range(m):
            length = min(m-i, n)
            # 小优化，length如果小于ans，则无需比较了
            if length > ans:
                ans = max(ans, helper(i, 0, length))
        for i in range(n):
            length = min(n-i, m)
            if length > ans:
                ans = max(ans, helper(0, i, length))
        return ans
        

动态规划算法

dp[i][j] 表示长度为i，结尾index为i-1的nums1数组与长度为j，结尾index为j-1的nums2数组的最长公共子数组的长度

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        ans = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = 0
                ans = max(dp[i][j], ans)
        return ans
        

动态规划算法优化

发现上述dp其实每次只依赖上一行左上角的值，也就是内层循环。可以优化一下空间复杂度。
但是为了避免左上角的值被覆盖，内层循环需要从右向左计算。

可以将空间复杂度降低为O(n)

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        dp = [0]*(n+1)
        ans = 0
        for i in range(1, m+1):
            for j in range(n, 0, -1):
                if nums1[i-1] == nums2[j-1]:
                    dp[j] = dp[j-1] + 1
                else:
                    dp[j] = 0
                ans = max(dp[j], ans)
        return ans
        

二分法+hash

TODO

输出子串

TODO