gpt4 book ai didi

c - 子集的不同总和数

转载 作者:太空狗 更新时间:2023-10-29 16:49:55 24 4
gpt4 key购买 nike

我有一组 N,对于 N>3,不同的整数,问题是找到给定集合的 3 个子集的所有不同的总和。 3 子集是基数为 3 的子集。

我知道愚蠢的方法是对所有可能的总和进行立方搜索,然后找出所有重复项。有没有更有效的方法来做到这一点?我正在用 C 编程。

编辑:如果说元素的数量增加了,我想知道一个通​​用的更快的算法。

最佳答案

如果您怀疑您可能有很多重复的总和,那么您可以先计算所有不同的 2 子集总和,然后对于您找到的每个不同的 2 子集总和,跟踪您找到的哪对子集给了您和。如果您所有的数字都不同,那么如果您找到另一对给您相同的总和,您应该将总和标记为“多个”,并且您可以根据需要删除为其存储的那对。现在你有一组 2 子集和,每个和都存储了一对,或者标记为“多个”。对于每个 2 子集总和,如果它被标记为“多个”,那么您将遍历原始集合中的所有数字,并记录您可以通过将每个数字添加到 2 子集总和来形成的所有 3 子集总和。否则,如果 2 子集总和未标记为“多个”并且您有一对 (a,b) 与之关联,那么您将执行相同的操作,只是在迭代原始数字集时跳过 a 和 b .这就是您获得所有不同的 3 子集总和的方式。如果你有 n 个数字并且它们使 N 个不同的 2 子集和,那么如果你在算法的两个阶段使用哈希表来检测重复项,这种方法的复杂度是 O(nN),这可能比蛮力要好得多强制 O(n^3 log n),尤其是当你有一组相当密集的整数时。

关于c - 子集的不同总和数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17898678/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com