在一个集合(包含负数)中快速找到m(几百)个数,使得该m个数的和为0


如题。
希望能找到一种较快的方法。
已邀请:

吃不下的/fan

赞同来自: beta


这个应该属于k-sum问题吧,戳这里有答案:

k-SUM can be solved more quickly as follows.

For even k: Compute a sorted list S of all sums of k/2 input elements. Check whether S contains both some number x and its negation −x. The algorithm runs in O(n^(k/2)logn) time.

For odd k: Compute the sorted list S of all sums of (k−1)/2 input elements. For each input element a, check whether S contains both x and a−x, for some number x. (The second step is essentially the O(n2)-time algorithm for 3SUM.) The algorithm runs in O(n^((k+1)/2)) time.

Both algorithms are optimal (except possibly for the log factor when k is even and bigger than 2) for any constant k in a certain weak but natural restriction of the linear decision tree model of computation. For more details,

要回复问题请先登录注册