Какие числа складываются в k?

Question

Я не уверен, как это сделать. Получив список чисел и число k, верните все пары чисел из списка, которые складываются до k. пройти список только один раз.

Например, учитывая [10, 15, 3, 7] и k из 17. Программа должна вернуть 10 + 7.

Как вы заказываете и возвращаете каждую пару, проходя по списку только один раз.

Answer 1

Используйте набор, чтобы отслеживать то, что вы видели. Время выполнения O (N), Пробел: O (N)

def twoAddToK(nums, k):
  seen = set()
  N = len(nums)
  for i in range(N):
    if k - nums[i] in seen:
      return True
    seen.add(nums[i])  
  return False

Answer 2

В качестве альтернативы коду Шона, который использует набор, есть также опция сортировки списка за O (N log N) времени (и, возможно, без лишних пробелов, если вам разрешено перезаписывать исходный ввод), и затем применение O (N) алгоритма для решения проблемы в отсортированном списке

Хотя асимптотическая сложность немного предпочтительнее использования хеш-наборов с точки зрения времени, поскольку O (N) лучше, чем O (N log N), я готов поспорить, что сортировка + однопроходный поиск значительно быстрее на практике.