Комбинации, добавляемые к нулю

Question

Данные пяти отсортированных списков: List1, List2, List3, List4, List5 с длиной n каждого. если любые 5 (int) чисел (1 из каждого списка), сумма до нуля возвращает true. Моя цель - обеспечить, чтобы алгоритм O (n). С головы до головы я могу думать о создании либо хэш-карты с суммой из 5 связанных списков или оценки 5 списков, таких как [o (n * n * n * n * n)]. Я ищу способы оптимизировать или уменьшить сложность, и я застрял.

Мой код в Python:

def getIndicesFromFiveArrays(List1,List2,List3,List4,List5,t): 
    a,b,c,d,e=0,0,0,0,0 
    while(List1[a]+List2[b]+List3[c]+List4[d]+List5[e]!=t): 
     b=b+1 
     if b==len(List2): 
      return (-1,-1) 
     if List1[a]+List2[b]+List3[c]+List4[d]+List5[e]<t: 
      a=a+1 
      b=b-1 
     c=c-1 
     d=d-1 
     e=e-1 
      if a==len(List1): 
       return (-1,-1) 
    return (a,b,c,d,e) 

EDIT 1: это не домашнее задание, кстати, вы можете проверить мои другие вопросы и убедитесь сами. спасибо ..

Answer 1

Если бы было 2 списка, вы бы взяли число из списка 1, а затем искали отрицательное значение этого числа в списке 2. Если вы заменили список 2 набором, общая сложность была бы равна O (п).

Если было 3 списка, вы взяли бы номер из списка 1, а затем один из списка 2 со сложностью O (n^2). Если вы заменили список 3 набором, общая сложность была бы O (n^2).

Поэтому я считаю, что общая сложность для 5 списков/множеств не может быть уменьшена ниже O (n^4).

Answer 2

Существует решение O (n^3), вдохновленное комментарием MRAB.

Сначала объедините каждое значение из списка 1 с каждым значением из списка 2 и сохраните его в наборе. Вызвать набор результатов 1 и 2, он имеет n^2 значения.

Далее следует комбинировать набор 1 и 2 со списком 3. Вызвать набор результатов 1and2and3, он имеет n^3 значения и принимает n^3 шага для построения.

Далее следует объединить списки 4 и 5. Вызвать набор результатов 4and5, он имеет n^2 значения.

Наконец, проверьте, соответствует ли какое-либо значение в наборе 4and5 обратному значению в наборе 1and2and3. Этот шаг занимает n^2 шага.

Этот подход использует пространство O (n^3) и время O (n^3).

Как указывает Karoly Horvath, на самом деле вам не нужно хранить набор 1and2and3, вы можете построить его на лету из набора 1 и 2 во время последнего шага. Этот подход использует только пространство O (n^2), но все же требует O (n^3) времени. Вот код:

l1 = [1,2,3,4,5,10] 
l2 = [1,2,3,4,5,11] 
l3 = [1,2,3,4,5,12] 
l4 = [1,2,3,4,5,13] 
l5 = [1,2,3,4,5,-46] 

def test(): 
    l1_2 = [a + b for a in l1 for b in l2] 
    set4_5 = set([a + b for a in l4 for b in l5]) 
    return any([True for x in l1_2 for y in l3 if -(x + y) in set4_5]) 

print test()