相反数

GitHub跳转原题关系图Canvas 关系图返回列表

用偏移量数组记录已出现整数，读到 x 时查询相反数 -x 是否存在。

OJ: shumeng

题目 ID: CSP201403A

难度:入门

标签:数组计数

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 样例流程
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定 NN 个互不相同的非零整数，统计其中有多少个无序相反数对，即满足 a+b=0a + b = 0 的 {a,b}\{a, b\}。

思路

朴素做法直接枚举所有下标对：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:49
 */
// brute.cpp：小数据暴力解，枚举每一对下标。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

int n;
int a[MAXN];

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[i] + a[j] == 0) {
                answer++;
            }
        }
    }

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

由于数值范围只有 [−1000,1000][-1000,1000]，用 seen[v+1000] 记录整数 v 是否已出现即可。读到当前数 x 时，先检查此前是否出现过 -x；若出现，答案加一；再标记 x 已出现。

样例流程

下面展示样例 1,2,3,−1,−21, 2, 3, -1, -2 的处理顺序：

读入 已出现过 -x? 答案 标记
1 -1 没有 0 标记 1
2 -2 没有 0 标记 2
3 -3 没有 0 标记 3
-1 1 有 1 标记 -1
-2 2 有 2 标记 -2

每对相反数只会在后读到的那个数处理时计数一次。输入互不相同，因此不会重复计数。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:49
 */
#include <bits/stdc++.h>
using namespace std;

const int OFFSET = 1000;
bool seen[2005];

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

    int n;
    cin >> n;

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (seen[-x + OFFSET]) {
            answer++;
        }
        seen[x + OFFSET] = true;
    }

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

复杂度

时间复杂度为 O(N)O(N)，seen 的长度固定，空间复杂度为 O(1)O(1)。

总结

值域较小时，存在性查询可直接用偏移量数组实现。关键顺序是先查 -x，再标记 x。