✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

顺丰-2026.03.15

1. 等距货架

问题描述

小基 正在整理一排长度为 的货架，第 个位置上放着一件编号为 的货物。

她想从中挑出若干个位置，要求同时满足下面两个条件：

• 挑出的货物编号完全相同。
• 这些位置编号从小到大看，能够组成一个等差数列。

请计算，最多可以挑出多少个位置。

输入格式

第一行包含一个整数 ，表示数据组数。

对于每组数据：

第一行包含一个整数 ，表示货架位置数量。

第二行包含 个整数 ，表示每个位置上的货物编号。

输出格式

对于每组数据输出一行一个整数，表示最多能挑出的元素个数。

样例输入

2
1
1
6
1 2 3 2 3 2

样例输出

1
3

数据范围

样例	解释说明
样例 1	第 组数据只有一个位置，所以答案是 。 第 组数据里，值为 的位置是 ，它们本身就是公差为 的等差数列，因此答案是 。

题解

问题的本质

这道题有两个条件必须同时满足：

1. 选出来的元素值要一样。
2. 选出来的位置要等距。

所以不能只看某个值出现了多少次。
如果某个值出现在位置 ，虽然一共出现了 次，但这三个位置并不能组成等差数列，不能一起选。

真正要做的是：
对每一种值，单独看它出现在哪些位置，然后在这串位置里找最长等差子序列。

第一步：按值分组

从左到右扫描数组，把每个值出现的位置记录下来。

如果值 出现的位置依次是：

那么原问题就变成了：

在严格递增的位置序列 中，最长等差子序列有多长？

每个值各算一次，最后取最大值即可。

第二步：在位置序列里做最长等差子序列

设当前位置序列为 。

定义状态 ：

表示以 结尾，公差为 的等差子序列最长长度。

现在枚举最后两个位置 ，其中 。
公差自然就是：

接下来分两种情况：

• 如果之前已经存在一个以 结尾、公差同样为 的序列，那么可以把 接到后面，长度变成 。
• 如果不存在，那就说明只能从 这两个位置重新开始，长度是 。

于是转移就是：

因为位置编号最大只有 ，所以公差 的范围最多是 到 ，直接按公差开数组就够了。

为什么这样做是对的

等差子序列最关键的信息只有两个：

• 最后一个位置是谁。
• 公差是多少。

只要这两个量确定了，前面能接多长就已经完全由更早的状态决定。
所以用 表示“以某个位置结尾、且公差固定”的最优结果，信息是完整的，不会漏掉答案。

当枚举到一对位置 时：

• 若前面有同公差的合法序列，就延长它。
• 若前面没有，就把这两个位置当成新序列的开头。

这正好覆盖了所有可能的等差子序列，因此最终取最大值就是答案。

复杂度分析

假设某个值一共出现了 次，那么处理这一组位置需要枚举所有位置对，复杂度是 。

所有值的出现次数之和正好是 ，因此总复杂度满足：

空间复杂度同样是单组 ，在 的范围内可以接受。

一个容易错的点

有些做法会先统计每个值的出现次数，再想办法补一个“位置等距”的判断。这样很容易绕弯。

更直接的想法是先按值分组，把“值相同”这个条件彻底消掉。
剩下就是标准的“位置序列最长等差子序列”问题，状态也会清楚很多。

参考代码

• Python

import sys
from array import array

input = lambda:sys.stdin.readline().strip()


def calc(pos, n):
    m = len(pos)
    if m <= 1:
        return m

    # f[j][d] 表示以 pos[j] 结尾、公差为 d 的最长长度。
    f = [array('H', [0]) * (n + 1) for _ in range(m)]
    ans = 1

    for j in range(m):
        row = f[j]
        pj = pos[j]
        for i in range(j):
            d = pj - pos[i]
            pre = f[i][d]
            cur = pre + 1 if pre else 2
            if cur > row[d]:
                row[d] = cur
                if cur > ans:
                    ans = cur

    return ans


def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))
        grp = [[] for _ in range(1001)]

        # 同一个值出现在哪些位置，全部记下来。
        for i, x in enumerate(arr, 1):
            grp[x].append(i)

        ans = 1
        for pos in grp:
            if len(pos) > ans:
                ans = max(ans, calc(pos, n))

        out.append(str(ans))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

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

int calc(const vector<int>& pos, int n) {
    int m = (int)pos.size();
    if (m <= 1) {
        return m;
    }

    // f[j][d] 表示以 pos[j] 结尾、公差为 d 的最长长度。
    vector<vector<unsigned short>> f(m, vector<unsigned short>(n + 1, 0));
    int ans = 1;

    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < j; ++i) {
            int d = pos[j] - pos[i];
            unsigned short cur = f[i][d] ? (unsigned short)(f[i][d] + 1) : 2;
            if (cur > f[j][d]) {
                f[j][d] = cur;
            }
            ans = max(ans, (int)f[j][d]);
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<vector<int>> grp(1001);
        for (int i = 1; i <= n; ++i) {
            int x;
            cin >> x;
            grp[x].push_back(i);
        }

        int ans = 1;
        for (const auto& pos : grp) {
            if ((int)pos.size() > ans) {
                ans = max(ans, calc(pos, n));
            }
        }

        cout << ans << '\n';
    }
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    static int calc(ArrayList<Integer> pos, int n) {
        int m = pos.size();
        if (m <= 1) {
            return m;
        }

        // f[j][d] 表示以 pos[j] 结尾、公差为 d 的最长长度。
        short[][] f = new short[m][n + 1];
        int ans = 1;

        for (int j = 0; j < m; j++) {
            int pj = pos.get(j);
            short[] row = f[j];
            for (int i = 0; i < j; i++) {
                int d = pj - pos.get(i);
                int cur = f[i][d] == 0 ? 2 : f[i][d] + 1;
                if (cur > row[d]) {
                    row[d] = (short) cur;
                }
                if (row[d] > ans) {
                    ans = row[d];
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();
        int t = fs.nextInt();

        while (t-- > 0) {
            int n = fs.nextInt();
            @SuppressWarnings("unchecked")
            ArrayList<Integer>[] grp = new ArrayList[1001];
            for (int i = 0; i <= 1000; i++) {
                grp[i] = new ArrayList<>();
            }

            for (int i = 1; i <= n; i++) {
                int x = fs.nextInt();
                grp[x].add(i);
            }

            int ans = 1;
            for (ArrayList<Integer> pos