某耀员工：同事都快40了，加个班疯狂3条朋友圈，不愧是优秀的演员！

某耀这位同事也是挺会整活。

加个班，一口气发三条朋友圈，灯光、工位、咖啡杯，可能还得配一句“继续战斗”。旁边人一看，活儿没见多干多少，氛围感先拉满了。

同事都快40了，还这么拼朋友圈营业，楼主直接来一句“不愧是优秀的演员”，这话有点损，但职场里确实常见。不是说加班不能发，谁累了发两句吐槽很正常。可有些人发得太像汇报演出，生怕领导没刷到，生怕大家不知道他还在公司。

职场最烦人的不是加班，是把加班演成一种人设。你干活就干活，别把旁边人都衬得像不努力一样。领导看了可能还挺感动，工位边上的兄弟估计只想翻白眼。

面试题：最长重复子数组

数组一长，最容易写错的不是循环，是你以为自己在找“重复子数组”，结果写着写着变成了“重复子序列”。

这俩差得挺远。

子数组必须连续。[1,2,3,2,1] 和 [3,2,1,4,7] 里面，最长重复子数组是 [3,2,1]，长度是 3。

不是把能对上的数字东捡一个西捡一个拼起来。

我见过不少代码，一上来就双指针，或者拿 HashMap 记位置，然后越写越乱。这个题第一眼我一般不太信那些花活，先把状态定义摆正。

假设有两个数组：

int[] a = {1, 2, 3, 2, 1};
int[] b = {3, 2, 1, 4, 7};

我们要找的是：

a 中某一段连续内容 == b 中某一段连续内容

这类“连续匹配”的题，动态规划其实很顺手。

别急着想 dp[i][j] 表示前多少个元素的最优解，那样容易绕进去。

我更喜欢这么定义：

dp[i][j] 表示：
以 a[i - 1] 结尾、以 b[j - 1] 结尾时，最长相同连续子数组的长度

注意，是“以它俩结尾”。

这句话很关键。

如果：

a[i - 1] == b[j - 1]

说明当前这两个位置能接上前面的连续匹配，那么：

dp[i][j] = dp[i - 1][j - 1] + 1

如果不相等，那就断了。

dp[i][j] = 0

这里不能取左边、上边的最大值。

这也是最长重复子数组和最长公共子序列最容易混的地方。子序列可以跳，子数组不能跳。断了就是断了，别硬续。

直接上代码。

publicclassSameBlockFinder{

publicintfindLength(int[] source, int[] target){
if (source == null || target == null) {
return0;
        }
if (source.length == 0 || target.length == 0) {
return0;
        }

int[][] hit = newint[source.length + 1][target.length + 1];
int longest = 0;

for (int i = 1; i <= source.length; i++) {
for (int j = 1; j <= target.length; j++) {
if (source[i - 1] != target[j - 1]) {
                    hit[i][j] = 0;
continue;
                }

                hit[i][j] = hit[i - 1][j - 1] + 1;

if (hit[i][j] > longest) {
                    longest = hit[i][j];
                }
            }
        }

return longest;
    }
}

这段代码没有什么玄学。

循环从 1 开始，是为了让 i - 1、j - 1 对应原数组下标，同时 hit[0][*] 和 hit[*][0] 天然就是 0，不用额外处理边界。

拿刚才那个例子走一下：

a = [1, 2, 3, 2, 1]
b = [3, 2, 1, 4, 7]

当扫到：

a[2] = 3
b[0] = 3

匹配长度变成 1。

继续扫到：

a[3] = 2
b[1] = 2

它能接上前面的 3，所以长度是 2。

再到：

a[4] = 1
b[2] = 1

长度就是 3。

这时候最长值更新为 3。

如果中间遇到不一样的数字，直接归零，不往旁边借。

我一般会加一段很土的本地校验，别上来就提交。很多边界问题，肉眼看不出来。

publicclassLocalCheck{

publicstaticvoidmain(String[] args){
        SameBlockFinder finder = new SameBlockFinder();

        check(finder.findLength(
newint[]{1, 2, 3, 2, 1},
newint[]{3, 2, 1, 4, 7}
        ), 3);

        check(finder.findLength(
newint[]{0, 0, 0, 0},
newint[]{0, 0}
        ), 2);

        check(finder.findLength(
newint[]{5, 6, 7},
newint[]{1, 2, 3}
        ), 0);

        check(finder.findLength(
newint[]{9},
newint[]{9}
        ), 1);
    }

privatestaticvoidcheck(int actual, int expect){
if (actual != expect) {
thrownew IllegalStateException("结果不对，actual=" + actual + ", expect=" + expect);
        }
        System.out.println("pass: " + actual);
    }
}

这几个用例不复杂，但够拦一批低级错误。

比如全是 0 的场景，能测出连续重复值有没有处理对。完全不相交的场景，能测出是不是误把不连续的东西拼起来了。单元素数组，能测边界。

空间复杂度是 O(m * n)。

如果数组长度只有几百、几千，这么写问题不大。代码清楚，排查也方便。

但如果数据量比较大，比如两个数组都上万，这个二维数组就不太舒服了。

因为 dp[i][j] 只依赖左上角的 dp[i - 1][j - 1]，不是依赖整张表，所以可以压缩成一维。

不过一维这里有个坑。

你不能从左往右更新。

因为 dp[j] 原本表示上一行的状态，当前行更新时要用的是“上一行左上角”的值。如果从左往右，会把上一行的数据覆盖掉。

所以要从右往左扫。

publicclassSameBlockFinderLite{

publicintfindLength(int[] source, int[] target){
if (source == null || target == null) {
return0;
        }

int[] row = newint[target.length + 1];
int longest = 0;

for (int i = 1; i <= source.length; i++) {
for (int j = target.length; j >= 1; j--) {
if (source[i - 1] == target[j - 1]) {
                    row[j] = row[j - 1] + 1;
if (row[j] > longest) {
                        longest = row[j];
                    }
                } else {
                    row[j] = 0;
                }
            }
        }

return longest;
    }
}

这个版本空间复杂度降到了 O(n)。

我平时写这种题，如果不是卡内存，第一版还是会先写二维。因为二维表更容易对着样例排查。等逻辑确认没问题，再压缩空间。

一维版本最容易漏掉的就是这句：

row[j] = 0;

不相等的时候必须清零。

别觉得上一轮留下来的值还能用。连续匹配已经断了，留下来就是脏数据。这个 bug 很隐蔽，样例简单时还真不一定测得出来。

这个题看起来是动态规划，其实考的是一句话：连续，就只能从左上角接；接不上，就清零。

记住这个判断，代码就不会散。