这不会是一次深入的评论，但我想专注于设计的某个特定方面。

每当我看到人们说他们想要高性能代码，但随后看到有人std::unordered_set使用……这让我很恼火。与实际性能更好的替代方案相比，它非常昂贵。哦，是的，在大多数情况下，它std::unordered_set比大多数其他选项（例如或大多数其他基于节点的容器）的性能要std::set高得多。是的，假设某些使用模式和足够大的数据量，它std::unordered_set 可能是性能最高的选择。但是！如果你真的想要性能，你应该像躲避瘟疫一样避免这些使用模式。

或者换句话说：如果您真的想要获得最佳性能，那么您应该寻找避免需要的方法std::unordered_set。

在这种情况下，其实很容易避免这种情况。你使用它来做的就是保证解决方案集中的每个三元组都是唯一的。但有一种更简单的方法可以做到这一点。

您所要做的只是按字典顺序检查元组。您可以向上或向下，这无关紧要；我将通过向下进行说明。

1. 首先从：

   • 十2=十02= n十2=十02=nx^2={x_0}^2=n和x =十0= ⌊n−−√⌋十=十0=⌊n⌋x=x_0=\lfloor\sqrt{n}\rfloor（即整数平方根，而不仅仅是平方根）；并且
   • 是2=是02= n −十02是2=是02=n−十02y^2={y_0}^2=n-{x_0}^2和是=是0= ⌊n −十02−−−−−−√⌋是=是0=⌊n−十02⌋y=y_0=\lfloor\sqrt{n-{x_0}^2}\rfloor。

   这意味着是2=是02= n − （十02+是02）是2=是02=n−（十02+是02）z^2={z_0}^2=n-({x_0}^2+{y_0}^2)和是=是0= ⌊n − （十02+是02）−−−−−−−−−−−−√⌋是=是0=⌊n−（十02+是02）⌋z=z_0=\lfloor\sqrt{n-({x_0}^2+{y_0}^2)}\rfloor。如果这是解决方案，请记录下来。如果不是，请继续。

2. 减少是是y，检查是是z每次检查是否得到三元组。当是是z大于是是y。

3. 减少十十x并计算是是y。 如果十十x小于是是y你已经完成了。否则，转到 2。

我忽略了一些棘手的细节，但其想法是你会得到如下结果：

If n = 129:
(11,2,2)
(10,5,2)
(8,8,1)
(8,7,4)

也就是说，结果是按（相反）顺序生成的。

由于结果是按可预测的顺序生成的，因此很容易避免重复工作，并且除了元素顺序之外，结果是“相同”的。这意味着不需要std::unordered_set……不需要std::sort()……没有浪费的工作。

不仅如此，由于您无需在知道最终结果之前生成所有结果（因为您无需跟踪已看到的结果以避免重复），因此您可以即时生成结果。我推测最终目标是打印结果；好吧，没有必要将所有结果放在容器中然后打印；您可以随时打印。

您可以将其实现为算法，也可以将其实现为范围生成器。后者功能更强大，但更复杂。因此，我将用算法来说明：

template<std::ranges::output_range<std::array<int, 3> const&> R>
constexpr auto find_sum_of_squares_triplets_for(R&& out, int n) -> std::ranges::borrowed_iterator_t<R>
{
    // implement your algorithm...
    if (is_triplet(x, y, z))
        // write std::array{x, y, z} to out
}

总结一下：

• 按字典顺序搜索三元组，这样就可以避免重复的结果，而无需排序或采用昂贵的构造std::unordered_set。
• 直接输出结果；不要将它们存储在容器中并返回容器。（如果有人想要将结果放在容器中，他们可以使用std::back_inserter或std::ranges::to()将它们放入容器中。）

另外，我很确定有一个常数时间方程可以检查是否有任何结果。您可能想立即执行此操作，看看运行循环是否有任何意义。

indi算法问题，但有几个风格问题引起了我的注意。

我们可以使用 来分解出许多重复的类型名称using。

• std::array<unsigned int, 3>
• std::unordered_set<std::array<unsigned int, 3>, ArrayHash>

您选择的实际名称由您决定，但类似于以下内容。

struct ArrayHash;

using uint_arr3 = std::array<unsigned int, 3>;
using set_t = std::unordered_set<uint_arr3, ArrayHash>;

此外，您的代码使用不一致的缩进。善待您的大脑吧。您花在阅读代码（包括您自己的代码！）上的时间比编写代码的时间还多。

解决这些问题：

#include <array>
#include <algorithm>
#include <cmath>
#include <unordered_set>

struct ArrayHash;

using uint_arr3 = std::array<unsigned int, 3>;
using set_t = std::unordered_set<uint_arr3, ArrayHash>;

struct ArrayHash {
    // Custom hash function for std::array<unsigned int, 3>
    std::size_t operator()(const uint_arr3& arr) const {
        std::size_t hashValue = 0;
        for (const auto& elem : arr) {
            hashValue ^= std::hash<unsigned int>()(elem) + 0x9e3779b9 + (hashValue << 6) + (hashValue >> 2);
        }
        return hashValue;
    }
};

set_t findUniqueTriplets(const unsigned int &n) {
    const int N_ROOTED = std::sqrt(n);
    set_t unique_triplets;

    for (unsigned int one = 1; one <= N_ROOTED; ++one) {
        const unsigned int one_squared = one * one;
        for (unsigned int two = 0; two <= N_ROOTED; ++two) {
            const unsigned int sum_squares = one_squared + two * two;

            if (sum_squares > n) {
                break;
            }

            const unsigned int remaining = n - sum_squares;
            const unsigned int three = std::sqrt(remaining);

            if (three * three == remaining) {
                uint_arr3 triplet = {one, two, three};
                std::sort(triplet.begin(), triplet.end());
               (void)unique_triplets.insert(triplet);
            }
        }
    }
  
    return unique_triplets;
}

算法

为了更加实际地了解 indi 所谈论的一些内容，让我们采用您的基本方法并仅进行一些更改。

• 显然我还没有将其分解成一个函数。
• y我在每个内循环中都以 的值开始x。例如，如果我们考虑了 x = 4, y = 8；那么就没有必要考虑 x = 8, y = 4。余数将相同，最终结果将重复。
• 内循环中有两个保护。第一个直接来自您的代码。如果没有余数，则循环结束。没有必要进一步检查。第二个通过确定根小于三元组的第二个元素并继续进行下一次循环迭代来防止重复，或者如果余数不是完全平方则继续进行下一次循环迭代。

int main() {
    constexpr unsigned int n = 1000;

    for (unsigned int x = 0; x < std::sqrt(n); ++x) {
        for (unsigned int y = x; y < std::sqrt(n); ++y) {
            unsigned int remainder = n - x * x - y * y;
            unsigned int root = std::sqrt(remainder);
            if (remainder <= 0) break;
            if (root < y || root * root != remainder) continue;

            std::cout << x << ", " << y << ", " << root << '\n';
        }
    }
}

您不需要像我一样打印到标准输出，但是循环内部可以将该三元组放回到 中std::vector<std::array<unsigned int, 3>>。

补充 indi 和 Chris 的答案：

为三元组创建新类型

该算法看起来非常混乱，因为您使用 rawstd::array<unsigned int, 3>来存储三元组。这要求您创建一个哈希函数，您必须将其显式传递给std::unorderded_set，并且必须显式对它们进行排序。考虑创建一个struct Triplet来处理所有这些：

struct Triplet {
    std::array<unsigned int, 3> values;

    Triplet(unsigned int a, unsigned int b, unsigned int c): values{{a, b, c}} {
        std::ranges::sort(values);
    }
};

template<>
struct std::hash<Triplet> {
    std::size_t operator()(const Triplet& triplet) const noexcept {
        return /* hash of a, b and c */;
    }
};

现在你可以像这样编写代码：

std::unordered_set<Triplet> findUniqueTriplets(unsigned int n) {
    …
    unique_triplets.emplace(one, two, three);
    …
}

创建自己的类型后，您可以做很多事情。例如，Chris 提到按字典顺序检查三元组。您可以添加一个operator++()to Triplet，将三元组更新为按字典顺序排列的下一个三元组。然后，您只需使用一个简单的循环即可搜索它们。

另一种选择是创建一个三元组迭代器，该迭代器仅返回平方和等于某个值的三元组。结合 C++23 的范围，您可以使主算法如下所示：

std::unordered_set<Triplet> findUniqueTriplets(unsigned int n) {
    return triplets_with_sum_square(n) | std::ranges::to<std::unordered_set>;
}