c++ - 在数组中找到四个元素，其总和等于给定数字 X

Question

<分区>

Answer 1

您可以在 O(n^2) 中完成。适用于重复和负数。

edit 正如 Andre 在评论中指出的那样，时间与哈希的使用有关，它具有“最坏情况”(尽管它比中彩票的可能性要小)。但您也可以用平衡树(Java 中的 TreeMap)替换哈希表并获得稳定的 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将从哈希中找到)