Blind 75 — Вопросы по программированию и техническому интервью — серия объяснений

Проблема:

Учитывая массив целых чисел nums и целое число target, вернуть [the] индексы [в nums array] из двух чисел таким образом, чтобы в сумме они составляли целевое значение.

Ограничения:

  1. Вы можете НЕ использовать один и тот жеэлемент дважды.
  2. Существует только один правильный ответ.
  3. 2 ‹= nums.length ‹= 104
  4. -109 ‹= числа[i] ‹= 109
  5. -109 ‹= цель ‹= 109

Объяснение:

Эта проблема в голове на самом деле довольно проста; вы проходите через массив и для каждого числа в этом массиве проверяете, есть ли в этом массиве другое число, которое в сочетании с вашим первым числом составляет цель.

Решение №1 — Вложенные циклы For — O(n²)

Используя объяснение в голове, довольно легко найти решение грубой силы. Вы проходите через массив, используя цикл for, затем вложенныйв этом цикле for вы снова проходите массив, проверяя, соответствует ли значение nums в первом цикле for и значение numsво втором цикле for складываются в цель, и если это так, возвращаются эти два индекса.

Здесь я устанавливаю переменную len_nums, так как длина массива nums используется более одного раза. Первый цикл for проходит от 0 до конца массива минус 1. Это связано с тем, что вы не можете использовать одни и те же индексы дважды, как указано в ограничениях, а второй цикл for выполняет цикл до конечного значения. Второй цикл for проходит от i + 1, потому что нет необходимости проверять от 0 до len_n, поскольку это привело бы к многократной проверке значений и снизило бы нашу эффективность. Затем мы проверяем, соответствуют ли два значения числа целевому и возвращают ли они эти индексы. Нет необходимости помещать оператор return после цикла for, потому что, как указано в ограничениях, всегда будет решение.

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    len_nums = len(nums)
   
    for i in range(0, len_n — 1):
      for j in range(i + 1, len_n):
        if nums[i] + nums[j] == target:
          return [i, j]

Решение №2 — Хэш-таблица — O(n)

Это определенно более сложное решение, которое требует знания хэш-таблиц. Хотя, если вы сможете придумать это решение, эффективность времени будет намного выше, чем у предыдущего решения. Как и в предыдущем решении, мы сохраняем длину массива nums. Мы вводим новую переменную, которая будет нашей хеш-таблицей: hashtable. Инициализируется с помощью dict(), который в Python содержит ключи и значения. Первый цикл for проходит по массиву nums, использует его значения в качестве ключей и сохраняет индекс i в качестве значение для этого ключа. Это имеет больше смысла, если посмотреть на второй цикл for, где мы можем проверить, содержит ли hashtable определенное значение. Это определенное значение, которое мы будем проверять, является дополнением target и текущего значения nums[i], это хранится в переменной compliment, поскольку ее значение будет использоваться несколько раз. Затем идет заключительная часть этого решения, проверяющая, является ли комплимент значением в хеш-таблице, но НЕтекущим значением nums[i], так как в ограничениях мы не можем вернуть один и тот же индекс дважды. И поскольку у нас гарантированно есть решение, нет необходимости в операторе return после цикла for, и вы решили LeetCode 1. Two Sum!

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashtable = dict()
    len_n = len(nums)
 
    for i in range(len_n):
      hashtable[nums[i]] = i
 
    for i in range(len_n):
      compliment = target — nums[i]
 
      if compliment in hashtable and i != hashtable[compliment]:
        return [i, hashtable[compliment]]

Информация:

Веб-сайт: nkwade.dev
LinkedIn: linkedin.com/in/nkwade
GitHub: github.com/nkwade
Электронная почта: [email protected]