[sum = x的数组中的4个值

Question

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

例如数组= {1,3,4,5,6,9,4}有人可以一步一步很好地解释如何检查总和。8。只需要帮助visualization这个过程。

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 pair) value (pair of indices of df) 
    myDict = { (i+j):[i,j]  for i in range(0,len(df)) for j in range(i,len(df)) if not i == j}

    # iterate over pairs and find a sum of 'x'
    for k1, k2 in [[a,b] for a in myDict.keys() for b in myDict.keys() if (a+b) == x]: 
        if not myDict[k1] == myDict[k2]:
            return [df[myDict[k1][0]],df[myDict[k1][1]],df[myDict[k2][0]],df[myDict[k2][1]]]

    return []

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

注意，此方法与对גלעד-ברקן（注释）的描述非常接近，并在您的示例中进行了解释。