如何求数组中不重复整数的和？C++代码测试用例异常排查

核心问题分析 #

你的代码存在两个关键问题：

1. 内层循环条件错误
   原代码中内层循环的条件是j < i-1，这意味着检查第i个元素时，只会对比前i-1个元素之前的元素，漏掉了第i-1个元素。以失败的测试用例为例，当i=4（对应元素-1）时，循环只检查j=0、1、2，没有对比j=3的元素（同样是-1），导致重复的-1被错误累加，最终总和比预期少1。

2. 使用非标准变长数组
   int sum[size];属于C风格的变长数组（VLA），这并不是标准C的特性，在部分编译器中可能无法通过编译或产生未定义行为。标准C中应该使用动态容器（如std::vector）来存储运行时确定大小的数组。

修正后的代码 #

#include <iostream>
#include <vector>

int main() {
    int summation = 0;
    int size;
    std::cin >> size;
    std::vector<int> nums(size); // 使用vector替代变长数组
    for (int i = 0; i < size; ++i) {
        std::cin >> nums[i];
    }

    for (int i = 0; i < size; ++i) {
        bool isUnique = true;
        // 修正循环条件：检查从0到i-1的所有元素
        for (int j = 0; j < i; ++j) {
            if (nums[i] == nums[j]) {
                isUnique = false;
                break;
            }
        }
        if (isUnique) {
            summation += nums[i];
        }
    }

    std::cout << summation << std::endl;
    return 0;
}

优化建议（可选） #

如果数组规模较大，上述双重循环的时间复杂度为O(n²)，效率较低。可以使用std::unordered_set来优化，时间复杂度可降至O(n)：

#include <iostream>
#include <vector>
#include <unordered_set>

int main() {
    int summation = 0;
    int size;
    std::cin >> size;
    std::vector<int> nums(size);
    std::unordered_set<int> seen;

    for (int i = 0; i < size; ++i) {
        std::cin >> nums[i];
        // 如果元素不在集合中，累加并加入集合
        if (seen.find(nums[i]) == seen.end()) {
            summation += nums[i];
            seen.insert(nums[i]);
        }
    }

    std::cout << summation << std::endl;
    return 0;
}

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