найти четыре целых числа, которые суммируются с заданным значением

Question

Дана группа из n целых чисел - S , принадлежащая ℤ.Все целые числа в S находятся в диапазоне от 0 до 100 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), потому что мы никогда не смотрим на кандидатов в суммах [idx] более одного раза каждый, и есть n ^ 2 из этих кандидатов. Эта часть, вероятно, может быть улучшена, но не поможет общей сложности.