如何用C++解决正负整数配对问题？求更简单实现方法

你的需求是从包含正负整数的数组中，找出所有存在对应相反数的正整数，然后输出对应的正负对（示例中是按正整数升序排列输出）。先说说你贴的这段代码的问题：

• 效率极低：用双重循环遍历所有元素对，时间复杂度是O(n²)，数组长度大时会非常慢
• 输出重复：如果数组里有多个相同绝对值的元素（比如输入里的-5出现两次），会多次把5存入vector，导致输出重复的5,-5对
• 输出顺序混乱：完全依赖双重循环中找到元素对的顺序，不符合示例的升序要求

下面给你两种更简单高效的实现方式：

方法一：哈希集合+有序集合（匹配示例升序输出） #

这种方式既能高效查找，又能自动去重并按升序排列结果，完全贴合示例输出要求：

#include <iostream>
#include <unordered_set>
#include <set>
using namespace std;

void printPairs(int arr[], int n) {
    // 存储数组所有元素，用于O(1)时间判断相反数是否存在
    unordered_set<int> numSet;
    for (int i = 0; i < n; ++i) {
        numSet.insert(arr[i]);
    }

    // 存储符合条件的正整数，自动去重并升序排列
    set<int> validPositives;
    for (int num : arr) {
        // 只处理正整数，且它的相反数存在于数组中
        if (num > 0 && numSet.count(-num)) {
            validPositives.insert(num);
        }
    }

    // 输出结果
    for (int num : validPositives) {
        cout << -num << " " << num << " ";
    }
}

int main() {
    int arr[] = {4,5,8,3,2,-5,-8,-4,-2,-3,-5,8,-8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printPairs(arr, n);
    return 0;
}

代码说明： #

1. unordered_set<int> numSet：把数组所有元素存入集合，判断某个数是否存在的时间是O(1)，比原代码的遍历快得多
2. set<int> validPositives：自动对存入的正整数去重并升序排序，保证输出顺序和示例一致
3. 整体时间复杂度是O(n)（存入元素） + O(n)（遍历筛选） + O(k log k)（k是符合条件的正整数个数，排序），远优于原代码的O(n²)

方法二：哈希集合+去重标记（按元素首次出现顺序输出） #

如果不需要升序，只需要按正整数在数组中第一次出现的顺序输出，可以用这种更简洁的写法：

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

void printPairs(int arr[], int n) {
    unordered_set<int> numSet;
    unordered_set<int> printed; // 标记已输出的正整数，避免重复

    for (int num : arr) {
        numSet.insert(num);
    }

    for (int num : arr) {
        // 满足：正整数、存在相反数、未输出过
        if (num > 0 && numSet.count(-num) && !printed.count(num)) {
            cout << -num << " " << num << " ";
            printed.insert(num);
        }
    }
}

int main() {
    int arr[] = {4,5,8,3,2,-5,-8,-4,-2,-3,-5,8,-8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printPairs(arr, n);
    return 0;
}

代码说明： #

• printed集合用来记录已经输出过的正整数，避免重复输出同一对
• 输出顺序是正整数在数组中第一次出现的顺序，比如输入里4先出现，就先输出4,-4

内容的提问来源于stack exchange，提问作者Arcshahi