algorithm - 找到四个总和为给定值的整数

Question

给定一组 n 个整数 - S 属于 ℤ。S中的所有整数都在0到⌈nlgn⌉之间。
我需要找出 S 中是否有 4 个整数的和等于给定数字 X。

我知道有一个使用散列的O(n²)的解决方案，还有一些O(n²lgn).

是否有可能在不使用哈希的情况下在 n² 时间内解决这个特定问题？

如果使用哈希，O(n²) 是最坏的情况还是它的预期？

Answer 1

伪代码:

sums = array of vectors of size (n log n) * 2

for index1, num1 in numbers:
    for index2, num2 in numbers:
        sums[num1 + num2].append((index1, index2))

idx1 = 0
idx2 = x
while idx1 < idx2:
    if any pair in sums[idx1] doesnt share an index with any pair of sums[idx2]:
        any of those combinations generates the sum x
    idx1 += 1
    idx2 -= 1

由于数字在一个小范围内，我们不需要散列，我们可以使用以总和为索引的简单数组。为了生成总和，我们花费了 O(n^2) 时间。然后检查是否有一个总和，它也是 O(n^2) 因为我们从来没有多次查看 sums[idx] 中的候选者，并且有 n^2 个候选者。这部分可能可以改进，但不会帮助整体复杂性。