C++实现从std::vector筛选非勾股三元组的问题求助

代码中的核心问题 #

• 浮点数精度误差：用pow()计算整数平方会引入精度问题，比如pow(3,2)可能返回8.999999999999998而非精确的9，导致判断条件失效，应该直接用整数乘法a*a替代。
• 三元组判断逻辑不全：原代码只检查了input[i]作为直角边、input[j]作为直角边、input[k]作为斜边的情况，但勾股三元组的三个数可以是任意顺序（比如input[i]可能是斜边），导致大量有效三元组无法被识别。
• 重复检查效率低下：三重循环全量遍历所有索引组合，会重复检查相同的三元组，且未优化遍历顺序，浪费计算资源。

修正后的实现思路 #

1. 先找出输入中所有属于勾股三元组的元素，存入无序集合（std::unordered_set）自动去重；
2. 遍历输入向量，只保留不在该集合中的元素；
3. 检查三元组时覆盖所有可能的组合：判断三个数中是否存在任意两个数的平方和等于第三个数的平方，同时确保三个数互不相同。

修正后的代码 #

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

// 判断三个不同整数是否构成勾股三元组（支持任意顺序）
bool isPythagorasTriplet(int x, int y, int z) {
    long long x_sq = static_cast<long long>(x) * x;
    long long y_sq = static_cast<long long>(y) * y;
    long long z_sq = static_cast<long long>(z) * z;
    // 覆盖所有平方和的可能组合
    return (x_sq + y_sq == z_sq) || (x_sq + z_sq == y_sq) || (y_sq + z_sq == x_sq);
}

std::vector<int> pythagorasTriplet(std::vector<int> input) {
    std::unordered_set<int> triplet_elements;

    // 遍历不重复的三元组组合（i<j<k），避免重复检查
    for (size_t i = 0; i < input.size(); ++i) {
        for (size_t j = i + 1; j < input.size(); ++j) {
            for (size_t k = j + 1; k < input.size(); ++k) {
                int a = input[i];
                int b = input[j];
                int c = input[k];
                if (isPythagorasTriplet(a, b, c)) {
                    // 将三元组的三个元素加入集合
                    triplet_elements.insert(a);
                    triplet_elements.insert(b);
                    triplet_elements.insert(c);
                }
            }
        }
    }

    // 构建结果：保留不属于任何三元组的元素
    std::vector<int> notTriplets;
    for (int num : input) {
        if (triplet_elements.find(num) == triplet_elements.end()) {
            notTriplets.push_back(num);
        }
    }

    return notTriplets;
}

int main() {
    std::vector<int> input = {6, 25, 5, 3, 7, 24, 4, 23};
    std::vector<int> noTriplets = pythagorasTriplet(input);

    for (int num : noTriplets) {
        std::cout << num << std::endl;
    }

    return 0;
}

额外说明 #

• 使用long long存储平方值：避免较大整数平方后超出int范围导致溢出；
• 采用i<j<k的遍历方式：大幅减少重复检查次数，提升运行效率；
• 无序集合去重：确保同一个元素即使属于多个三元组，也只会被标记一次。

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