📝 题目大意

给定 $2N$ 个人排成一排，每人穿一种颜色的衣服，颜色编号为 $1$ 到 $N$，每种颜色恰好出现两次。求有多少种颜色，满足该颜色的两个人之间恰好隔着一人。

💡 解题思路

1. 题目分析：题目要求统计"两个人之间恰好隔着一人"的颜色数量。在数组中，这意味着该颜色的两个位置下标之差恰好为 $2$。例如位置 $i$ 和 $i+2$，中间只有一个位置 $i+1$。数据范围 $N \leq 100$ 很小，$O(N)$ 即可通过。

2. 算法推导：

   • 遍历数组一次，用 firstPos[color] 记录每种颜色第一次出现的位置（下标从 $0$ 开始）。
   • 当遇到某颜色的第二次出现时，计算当前位置与第一次出现位置的距离 i - firstPos[color]。
   • 若距离等于 $2$，说明中间恰好隔了一人，答案加一；否则不满足条件，忽略。
   • 该算法只需一次线性扫描，无需排序或额外数据结构。

3. 边界与细节：

   • 每种颜色恰好出现两次，因此 firstPos[color] 在第二次出现时一定已被赋值，不会出现未定义行为。
   • 注意下标从 $0$ 开始，若距离为 $2$ 则中间恰有 $1$ 个元素。若数组下标从 $1$ 开始则距离为 $2$ 时中间也只有 $1$ 个元素，结论一致。
   • $N=1$ 时，只有两个位置，距离为 $1$，答案为 $0$，边界情况正确。

⏱️ 复杂度分析

• 时间复杂度：遍历数组一次，每次操作 $O(1)$，总复杂度 $O(N)$。
• 空间复杂度：firstPos 数组大小为 $N+1$，A 数组大小为 $2N$，均为 $O(N)$。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(2 * N);          // 存放 2N 个人的颜色
    for (int i = 0; i < 2 * N; i++) {
        cin >> A[i];
    }

    vector<int> firstPos(N + 1, -1); // 记录每种颜色第一次出现的位置，初始化为 -1
    int count = 0;                    // 满足条件的颜色数量

    for (int i = 0; i < 2 * N; i++) {
        int color = A[i];
        if (firstPos[color] == -1) {
            // 第一次遇到该颜色，记录位置
            firstPos[color] = i;
        } else {
            // 第二次遇到该颜色，检查距离是否为 2
            if (i - firstPos[color] == 2) {
                count++;
            }
        }
    }

    cout << count << endl;
    return 0;
}