官方题解｜数组片段匹配

T2 - 数组片段匹配

注意题目中标注要求满足条件的长度相同的子数组中，只需要 $\bf{存在}$ 数对 $p(x_i, y_i) (1 \le i \le k)$ 其中 $x_i = y_i$ 即可。

这点提示我们要关注相同的元素。那么对于两个相同的元素，各自形成的子数组，如果两者在原数组中距离较远，则包含其子数组长度越短，反之，包含其子数组的长度越长。

在原数组中令 $a_i = b_j(1 \le i < j \le n)$ 这个长度可以拆分成两个部分 $x$ 和 $y$，其中 $x = a_i, y = n - a_j$，那么最终我们要求的答案就是枚举数组中相邻的相同数字的位置 $x + y$ 即 $n - (a_j - a_i)$ 最大的就是答案。

若数组中没有重复数字，显然不存在满足条件的两个子片段。

AC代码

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 150000;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        int pre[N + 1], max_len = -1;
        memset(pre, -1, sizeof pre);
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            if (pre[x] != -1)
                max_len = max(n - (i - pre[x]), max_len);
            pre[x] = i;
        }
        cout << max_len << '\n';
    }
    return 0;
}

复杂度分析

代码实现上，遍历数组 $a$，令外使用一个数组 $pre$ 记录数字 $x$ 在数组中出现的上一个位置，随着遍历不断更新，得到答案。时间复杂度为 $O(n)$。