Проблема алгоритма: выбрать по одному числу из каждого из пяти массивов, проверить, может ли их сумма быть 2018?

Question

проблема :

существует пять массивов неотсортированных чисел и выберите только одно число из каждого массива. проверьте, может ли сумма пяти чисел равняться 2018. Если возможно, верните true. иначе верните false.

мое решение:

самое наивное ...

sort the array in descending order
for a in arr1:
  for b in arr2:
     for c in arr3:
        for d in arr4:
           for e in arr5:
              if a+b+c+d+e == 2018:
                  return true
return false

результат моего решения:

ограничение по времени

---

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

Answer 1

Простая идея. Составьте отсортированный список ABC сумм первых 3 массивов. Составьте отсортированный в обратном порядке список DE сумм вторых 2-х массивов. Это пока занимает пространство O(n^3) и время O(n^3 log(n)).

А теперь начните суммировать элементы из ABC по элементам DE. Каждый раз, когда сумма меньше 2018, авансируйте ABC. Каждый раз, когда он выше, увеличивайте DE. Если вы найдете 2018, ваш ответ - True. Иначе это False. Это последнее сравнение O(n^3 + n^2). Общее время работы составляет O(n^3 log(n)).

Если вы хорошо разбираетесь в приоритетных очередях, вы можете сгенерировать ABC в отсортированном порядке, используя не более O(n^2) памяти. Однако время работы нельзя улучшить.

Answer 2

Ваш вопрос является производным от наиболее распространенного вопроса на собеседовании за все время, а именно: 2Sum .

---

Думаю, этот алгоритм может работать с этими тремя блоками:

• Счетчик для a + b (массив 1 и массив 2)
• Счетчик для c + d (массив 3 и arry 4)
• L oop через array 5

---

Технически это будет три отдельных блока для анализа временной сложности:

# This block is O(N ^ 2)
for element in array 1
    for element in array 2
        generate dictionary 1 # O(N) space
# This block is O(N ^ 2)
for element in array 3
    for element in array 4
        generate dictionary 2 # O(N) space

# This block is O(N ^ 3)
for element in dictionary 1
    for element in dictionary 2
        for element in array 5
            if statement

Тогда для пространственной сложности это будет два словаря, каждый порядок N, тогда память будет O (N).

---

Это будет решение O(N ^ 3) по времени и O(N) по пространству.

Python

import collections


def five_sum(A, B, C, D, E):
    AB = collections.Counter(a + b for a in A for b in B) # O (N ^ 2)
    CD = collections.Counter(c + d for c in C for d in D) # O (N ^ 2)

    # O (N ^ 3)
    for ab in AB: 
        for cd in CD:
            for e in E:
                if ab + cd + e == 2018:
                    return True
    return False


A = [0, 2000]
B = [0, 10]
C = [0, 10]
D = [0, -1]
E = [0, -1]

print(five_sum(A, B, C, D, E))

Вывод

True

Можно сделать его более эффективным, но я не думаю, что временная сложность изменится.