在数组中找到四个元素,其总和等于给定的数字X.

Question

我需要帮助才能找到一个找到的算法:

• 数组中的四个元素
• 其总和等于给定数字X.
• 在O(n ^ 2*log(n))

喜欢伪代码或c,c ++

Answer 1

你可以在O(n ^ 2)中完成.与重复和负数一起工作正常.

编辑安德烈在评论中指出,时间是使用哈希,这是"最坏情况"(虽然它不如在彩票中获胜).但是你也可以用平衡树(java中的TreeMap)替换hashtable并获得保证稳定的O(n ^ 2*log(n))解决方案.

Hashtable sums将存储两个不同元素的所有可能总和.对于每一个总和S,它返回一对索引i和j使得a[i] + a[j] == S和i != j.但最初它是空的,我们将在途中填充它.

for (int i = 0; i < n; ++i) {
    // 'sums' hastable holds all possible sums a[k] + a[l]
    // where k and l are both less than i

    for (int j = i + 1; j < n; ++j) {
        int current = a[i] + a[j];
        int rest = X - current;
        // Now we need to find if there're different numbers k and l
        // such that a[k] + a[l] == rest and k < i and l < i
        // but we have 'sums' hashtable prepared for that
        if (sums[rest] != null) {
            // found it
        }
    }

    // now let's put in 'sums' hashtable all possible sums
    // a[i] + a[k] where k < i
    for (int k = 0; k < i; ++k) {
        sums[a[i] + a[k]] = pair(i, k);
    }
}

让我们说吧X = a[1] + a[3] + a[7] + a[10].这个总和将被发现的时候i = 7,j = 10和rest = a[1] + a[3](索引1和3将从散列找到)

Answer 2

对我来说听起来像是家庭作业。但这就是我要做的。

首先对数字进行排序（这是你的 n*log(n)）。

现在，创建指向列表的指针，并使用前 4 个数字对其进行初始化。获得后，您可以检查 4 个当前数字的总和与总数。它应该小于或等于您的搜索总和（如果不是，您可以提前退出）。现在您需要做的就是遍历列表的其余部分，交替用列表中的当前值替换指针。这只需要发生一次（或者最坏的情况是 4 次），所以还有其他 n，这使得 n^2*log(n)

你需要跟踪一些逻辑来知道你的总和是否超过/低于你的总和以及下一步该做什么，但我将其作为你的家庭作业。