algorithm - 找到四个整数相加得出给定值

给定一组n个整数-s，它们属于_。
S中的所有整数都在0到⌈nlgn⌉之间。
我需要找出s中是否有4个整数的和等于给定的x。
我知道有一个使用散列的o（n2）解，还有一些其他的o（n2lgn）解。
有没有可能在n2时间内不使用散列就可以解决这个特定的问题？
如果使用散列，O（n2）是最坏的情况，还是它的预期？

最佳答案

伪码：

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），因为我们从来不会在每个和中查看候选项[idx]超过一次，并且这些候选项中有n^2个。这一部分可能会得到改善，但对整体的复杂性没有帮助。