Я пытаюсь решить следующий вопрос:
Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
Bonus: Can you do this in one pass?
Меня интересует бонусный вопрос.
Я думаю, что смогу сделать это за один проход и в O (k) пространстве. Однако я должен предположить, что числа неотрицательны.
Я делаю это, создавая массив bool размера k + 1 и помечая true как различия между каждым элементом и k. Если я когда-нибудь приду к элементу в массиве, который был помечен как «true», я верну true. Если нет, я возвращаю false. Более того, любой элемент x , который удовлетворяет k , пропускается, поскольку к этому ничего нельзя добавить, чтобы получить k.
Если я не предполагаю что-либо, я могу сделать это за два прохода, сначала найдя диапазон элементов в данном массиве, а затем определив размер мой логический массив соответственно и работает вышеупомянутый алгоритм.
Как вы думаете, возможно ли сделать это за один проход без каких-либо предположений?
Если вы хотите предоставить свое решение, не стесняйтесь! Просто скажи мне, что это то, что ты мне дашь, чтобы я мог сначала попытаться решить это сам, прежде чем я посмотрю, что ты написал.