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

Question

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

例如。数组 = { 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) 中，因为 map /字典中的插入和查找操作通常是 O(log n)。