Три Сумма ХэшМап Подход - PullRequest
Новая
       8

Три Сумма ХэшМап Подход

0 голосов
/ 06 февраля 2020

Привет, я не понимаю, как kl oop - это постоянное время. Если массив был [4,4,4,4,4,4], а цель была 12, то number_table [4] = [0,1,2,3,4,5] и затем kl oop будет повторяться пять раз нет? спрашивая себя, все ли i, j и k разные ... Это видео, кажется, говорит иначе? video 



def three_sum(nums, target):
  number_table = {}
  for i in range(len(nums)):
    if nums[i] in number_table.keys():
      number_table[nums[i]].append(i)
    else:
      number_table[nums[i]] = []
  for i in range(len(nums) - 1):
    for j in range(i + 1, len(nums)):
      partial_target = target - nums[i] - nums[j]
      for k in number_table[partial_target]:
        if len(set((i,j,k))) == 3:
          return (nums[i], nums[j], nums[k])
  return None

numbers = [4,4,4,4,4,4]
target = 12
three_sum(numbers, target)
print(three_sum(numbers,target))

1 Ответ

2 голосов
/ 06 февраля 2020

Когда вы доберетесь до этого самого внутреннего l oop, есть три случая:

  • k == i ← Это может произойти только один раз, потому что i может появиться только один раз в списке.
  • k == j ← Это может произойти только один раз, потому что j может появиться в списке только один раз.
  • k != i and k != j ← Это может произойти только один раз, потому что вы вернетесь, как только Бывает. (Примечание: код фактически проверяет, различны ли все три из i, j и k; но мы уже знаем, что i != j, поскольку j начинается с i + 1 и продолжается вверх, так что это эквивалентно просто проверке k != i and k != j.)

Итак, мы пробуем не более трех значений k; и 3 действительно является константой, по желанию.

...