时间戳

首页 > 解决方案 > sum = x 的数组中有 4 个值

algorithm - sum = x 的数组中有 4 个值

问题描述

我不需要这个代码。我想知道是否有人可以展示如何在一个大小为 n 的数组中找到 4 个整数，该数组在时间复杂度 n^2logn 中可能等于值 x。我尝试寻找视频，但发现它们很难跟随。根据我的理解，您创建了一个包含所有可能对的辅助数组？对它们进行排序，然后从较小的数组中找到 x 的总和？

例如。Array = { 1,3,4,5,6,9,4} 有人可以分步解释如何检查 8 的总和。只需要帮助可视化这个过程。

标签： algorithmtime-complexityanalysis

解决方案

# 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)。

推荐阅读