【leetcode】718 最长重复子数组（滑动窗口解法）

前言

这是今日的每日一题，但是leetcode题解里对滑动窗口的解法动图之类有特别强烈的误导性，导致一般很难写出滑动窗口的解法。我自己研究之后，将他们错误的流程图改编成正确的流程便于以后有类似需求可以想到。

原理

这个滑动窗口的写法跟一般滑动窗口写法不太一样，一般滑动窗口只要移动指针就完事了，这个滑动窗口其实不应该看成滑动窗口，而应该去找规律。leetcode题解里面对这题虽然动图意思对的，但是顺序以及注意点都有强烈误导性，导致正常人看了动图压根写不出这种循环。所以我拿别人图将顺序和过程以及注意点改造了下： 红线部分作为分界线，右边第一列为窗口长度，leetcode里5窗口那里搞个4，而且顺序还是反的，并且没有下面的4那行，极具误导性，让你想不到咋写。第二列就是2个数组的起始索引。这个图放出来，规律一下子就看出来了。for循环2个数组长度和，当i比数组大时，就是个分界线，窗口大小会以第二个数组为主导。索引方面，分界线前，下面那个数组起始索引恒为0，分界线后，上面那个数组索引恒为0。另一部分索引分界线前倒序，分界线后正序。第二个for循环就各自从起始索引开始，窗口长度结束进行对比即可。

代码

对着上面图，看下面代码，是不是就非常清晰了。 function maxLength(A:number[], B:number[], aStart:number, bStart:number, len:number){ let max = 0, count = 0; for (let i = 0; i < len; i++) { if (A[aStart + i] == B[bStart + i]) { count++; max = Math.max(max, count); } else { count = 0; } } return max; } function findLength(A: number[], B: number[]): number { let aLength= A.length let bLength= B.length let ret=0 let total = aLength + bLength ; for (let i = 0; i < total; i++) { let aStart = 0; let bStart = 0; let len = 0;//窗口长度 if (i < aLength) { aStart = aLength - i - 1; bStart = 0; len = i + 1; } else { aStart = 0; bStart = i - aLength; len = Math.min(bLength - bStart, aLength); } let maxlen = maxLength(A, B, aStart, bStart, len); ret = Math.max(ret, maxlen); } return ret };