4 значения в массиве с суммой = х

Question

Мне не нужен код для этого. Мне было интересно, если бы кто-нибудь мог показать, как найти 4 целых числа в массиве размера n, который мог бы равняться значению x во временной сложности n ^ 2logn. Я пытался искать видео, но мне было трудно следить за ним. Из моего понимания вы создаете вспомогательный массив из всех возможных пар? Сортировать их, а затем найти сумму х из меньших массивов?

Например. Array = {1,3,4,5,6,9,4} Может ли кто-нибудь очень подробно объяснить, как проверить сумму, скажем, 8. Просто нужна помощь для визуализации этого процесса.

Answer 1

# your input array 'df' and the sought sum 'x' 
df = [1,3,4,5,6,9,4]
x = 12

def findSumOfFour(df, x):
    # create the dictionary of all pairs key (as sum of a pair) value (pair of indices of 'df') 
    myDict = { (df[i]+df[j]):[i,j]  for i in range(0,len(df)) for j in range(i,len(df)) if not i == j}

    # verify if 'x' - a key 'k' is again a key in the dictionary 'myDict',
    # if so we only need to verify that the indices differ
    for k in myDict.keys():
       if x-k in myDict.keys() and not set(myDict[k]) & set(myDict[x-k]):
           return [df[myDict[k][0]],df[myDict[k][1]],df[myDict[x-k][0]],df[myDict[x-k][1]]]

    return []

solution = findSumOfFour(df,x)
print(solution)

Обратите внимание, что этот подход следует описанию גלעד-ברקן (комментарии), объясненному более подробно и на вашем примере.

Примечание 2, время выполнения в O (n ^ 2 log n), поскольку операции вставки и поиска в карте / словаре в общем случае - O (log n).