Сумма двух

А вот и давно обещанная следующая разминка. Мы получили массу удовольствия ища решение этой задачи, и не можем не поделиться.

Дано: массив случайных натуральных чисел X в случайном порядке, среди которых могут быть дубликаты. Целое число C.

Вопрос: может ли число C быть сформировано суммой двух элементов массива? Другими словами, существуют ли такие i, j, что X[i] + X[j] == C?

Очевидным способом ответ ищется за O(n^2). Требуется найти более быстрое асимптотически решение. Исходный массив (X) записан в файл построчно, целевая сумма (C) либо передаётся параметром, либо жёстко забита в код, если ваш язык реализации не умеет читать параметры.

В помощь вам специально подготовленный гист, в котором есть файлик на 100 000 чисел и перечислено несколько тестовых чисел с правильными ответами - тут можно проверять решение. Можно сразу скачать. Кстати, квадратичные решения на 100 000 на моём компьютере в Руби работают порядка 40 минут, так что стимул решить правильно вроде бы есть.

Решения оставляйте гистами, комментарий в эту статью или в гист. Просьба к решению прилагать команду для его запуска, типа ruby solution.rb 215500 или sbcl --script kuteiko.lisp 66613. Итоги будем подводить через неделю, в понедельник.

Мы приветствуем все решения, но людей из списка просим предоставить свои решения аккурат в следующий понедельник. До этого, пожалуйста, не портите другим программистам удовольствие. Можете просто отметиться в комментариях к этой статье, что, мол, решение есть. В понедельник мы напомним вам, что нужно решением поделиться. Эти люди: Андрей Кутейко, Сергей Качан, Саша Михальчук, Игорь Афонов, Павел Митин, Владимир Коварский. Всем остальным рекомендуем выкладывать решения сразу, чтобы спровоцировать обсуждение достоинств и недостатков и оживить программистскую мысль нашего коллектива.

Желаем всем удачи и хорошего развлечения!

Всегда ваши,
Дима, Лёша.