解题思路

什么是回文数组？

回文数组就是：正着读和倒着读一模一样。比如 4 1 2 1 4，倒过来读还是 4 1 2 1 4，所以它是回文数组。

怎么判断？

一个数组如果回文，那么它一定满足“对称相等”：

• 第 1 个数 = 第 n 个数；
• 第 2 个数 = 第 n-1 个数；
• ……
• 第 i 个数 = 第 n-i+1 个数。

用下标（从 0 开始）来说，就是 a[i] == a[n-1-i]。

我们只需要比较前半段的每一个数和它对称的那个数：

• 用 i 从 0 走到 n/2-1；
• 只要有一对不相等，就说明不是回文，输出 NO 并结束；
• 全部相等，就输出 YES。

验证样例： 4 1 2 1 4，比较 a[0]=4 和 a[4]=4 相等，a[1]=1 和 a[3]=1 相等，所以是回文，输出 YES。

参考代码

// P4508 回文数组：判断正序和倒序是否完全相同
#include <iostream>
using namespace std;
int main() {
    int n, a[1005];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i]; // 读入数组
    int ok = 1;
    for (int i = 0; i < n / 2; i++)
        if (a[i] != a[n - 1 - i]) { ok = 0; break; } // 头尾对称比较
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}

复杂度分析

设数组长度是 n。

• 时间：只需要比较 n/2 对对称的数，时间复杂度是 O(n)；
• 空间：需要一个能装 n 个数的数组，空间复杂度是 O(n)。