algorithm - 设计一个算法来检查给定集合中的 k 个整数加起来是否等于 x

Question

<分区>

Answer 1

1. 对数组进行排序
2. 取 k 个数字的组合(所有 n^(k-1) 个)
3. 对于每个组合，检查 x-sum(combination) 是否在数组中(二进制搜索，O(log(n)))。

最终复杂度:O(n^(k-1) * logn)

如果你有足够的空间 ( n^(k/2) 长度数组，你也可以在 O( n^(k/2) log(n) ) 中完成。

计算总和的复杂度为 O(1)，因为您可以重复使用为之前的组合所做的计算。如果您计算了 (a+b+c+d)，则 (a+b+c+e) = (a+b+c+d) -d +e。