718. 最长公共子串的长度 👌

718. 最长重复子数组

== 连续のLCS
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

//动态规划法，二维时空都是O(nm)，通法
func findLength(nums1 []int, nums2 []int) int {
    m, n := len(nums1), len(nums2)
    dp := make([][]int, m+1)
    res := 0                            //多的一句，用于判断连续
    for i := range dp {                 //注意range遍历= i 从0~m 左闭右开，取i+1;  或者1~m，左闭右闭
        dp[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {            
        for j := 1; j <= n; j++ {
            if nums1[i-1] == nums2[j-1] {
                dp[i][j] = dp[i-1][j-1] +1
            } else {
                dp[i][j] = 0                    //其实 没意义的，因为也不会选它，只是更完整
            }
            res = max(res, dp[i][j])
        }
    }
    return res                  //返回连续的数组个数
}
func max(x,y int) int {
    if x > y {
        return x
    }
    return y
}

//注意滚动数组会发生覆盖，要从后往前遍历
//滚动数组， 一维空间降为O(min(m,n))
func findLength(nums1 []int, nums2 []int) int {
    m, n := len(nums1), len(nums2)
    dp := make([]int, n+1)
    res := 0                            //多的一句，用于判断连续

    for i := 1; i <= m; i++ {      
        pre := 0                                   //引入临时数组，滚动      

        for j := 1; j <= n; j++ {
            temp := dp[j]                         // 1，tmp 记录的是二维dp矩阵正上方的值

            if nums1[i-1] == nums2[j-1] {
                dp[j] = pre + 1                 // 2，pre 记录的是二维dp矩阵左上方的值     
            } else {
                dp[j] = 0                       //这个else 蛮难理解？
            }
            res = max(res, dp[j])
            pre = temp                             // 3，右边顺序记录
        }
    }
    return res
}

func max(x,y int) int {
    if x > y {
        return x
    }
    return y
}