718.最长重复子数组

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

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

1. 这道题目不能用首尾指针方法的原因在于，尾指针不只是和另一个尾指针匹配，和另一个数组指针区间中的任何一个元素匹配都有可能改变当前最长重复子序列长度，也是这道题目的难点，如果考虑让尾指针和每一个元素遍历就是暴力的思想。

2. 滑动指针对齐法。每一次固定两个数组的头，匹配两个数组长度重合的队列，遍历时两个数组的指针只需要同步移动，这也是固定头部对齐的好处，不需要交错匹配。最长重复队列一定会在移动到某个位置时，被一对一同步上下匹配。如果把B作为固定串(相当于隧道)，A作为滑动串(火车),那么对齐时一定是从A刚进去隧道到A完全出隧道，长度为O(m+n)。时间复杂度O((m+n)*min(m,n))

3. 动规。dp[i][j]表示以A[i]和B[j]元素为结尾的最长重复子数组的长度。这道题又增加了我们对于dp数组含义设计的理解，一道动规题目一般来说要用dp来解决，那么对dp[i][j]进行状态转移时，肯定是只涉及到对i和j下标附近元素的访问和比较(A[i-1],A[i],A[i+1]),因此我们设计dp数组时，每次维护dp[i][j]时添加的元素肯定只能是A[i]和B[j]。所以回到这道题目，如果我们直接设计dp[i][j]表示长度为i和长度为j数组的最长重复数组长度，是肯定不行的，因为A[i]和B[0]~B[j-1]任意一个元素匹配都有可能改变重复数组长度。