每日一题：LeetCode-718. 最长重复子数组

2023-12-22
北京
本文字数：1235 字
阅读完需：约 4 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]输出：3解释：长度最长的公共子数组是 [3,2,1] 。

复制代码

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]输出：5

复制代码

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

思路

最开始脑袋里泛起来的思路就是暴力法，当然暴力法肯定是时间复杂度太高的，所以需要寻找优化思路

思路 - 记忆化

这道题里很直观的一个优化思路就是，已经比对过的位置是能够记录下一个以此位置开始的最长公共子串长度的，而且在本题约束下并没有什么副作用，可以直接拿来用那么记忆化这个思路应该是可以实现的，而且应该能起到一个比较好的优化效果的。

那么，怎么实现？

实现 - 动态规划

先从记忆化需要记录的内容开始，这个思路需要记录的其实是在两个数组的一组坐标下，其最长公共子串长度，这样的内容能够方便我们在后续搜索中能更快速的计算最长公共子串长度

一组坐标
便于后续计算

这俩要素一凑，感觉就是活脱脱一个动态规划思路呀，那就来看看动态规划的条件够不够：

定义和初始数据

dp[i][j]的含义即为在i、j这一组坐标下，最长公共子串长度。

至于初始数据，那就是子串的最后一个字符，它们后面在没有别的字符，所以最长公共子串长度要么为0，要么为1。

状态转移方程

如果当前位置字符相等，那么就看之后字符是否相等：dp[i][j] = dp[i+1][j+1] + 1

如果当前位置字符不相等，那么指定为 0：dp[i][j] = 0

是否有副作用

本题目下，并没有更多的限制条件，所以计算后面位置的最长公共子串长度，对于更靠前位置的坐标的结果不构成影响

至此，代码也基本就出来了。老样子，细节在代码注释

代码

func findLength(nums1 []int, nums2 []int) int {    m := len(nums1)    n := len(nums2)    // dp[i][j] 含义为    // nums1以下标 i 开始，nums2以下标 j 开始 的 公共子串长度    dp := make([][]int, m)    for i, _ := range dp {        dp[i] = make([]int, n)    }
    res := 0    for i := m - 1; i >= 0; i-- {        for j := n - 1; j >= 0; j-- {            if nums1[i] == nums2[j] {                // 相同时才能+1                if i != m-1 && j != n-1 {                    // 结果基于后面两位的比对结果                    dp[i][j] = dp[i+1][j+1] + 1                } else {                    // 其实是初始化动作，合并了                    dp[i][j] = 1                }            } else {                dp[i][j] = 0            }            if dp[i][j] > res {                res = dp[i][j]            }        }    }    return res}

复制代码

欢迎关注公众号交流更多题目~

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/b8477eceb65dbcc6f434acd15】。文章转载请联系作者。

半亩房顶

关注

人生那么长，能写多少bug？ 2018-11-16 加入

我希望，自己永远是自己。我希望，远离bug。

发布

暂无评论

创作场景

每日一题：LeetCode-718. 最长重复子数组

题目

思路

思路 - 记忆化

实现 - 动态规划

代码

半亩房顶

评论