实数数组上的函数，用于确定数组中的数字是否由数组中的每个数字组成

Question

我们有一个实数集/数组M。如果M中的s和t与r=s+t。目标是找到一个在O(n^2(中运行的算法(在伪代码中(，该算法决定M中的每个r是否组成。数组按升序排序。

我不知道如何在给定的时间复杂度下找到一个算法。提前感谢的每一次输入

Answer 1

由于O(N^2)是允许的，您可以简单地使用两个循环来检查所有对的和。散列映射中的所有数字，如果找到一对，则递减它们的计数。如果所有数字最后都有0计数，则意味着为每个元素找到了一个和对。简单的伪代码是：

def func(array):
map = {}
n = len(array)
result = [false]*n
for i in array:
map[i] += 1
for i in range(n):
for j in range(n):
temp = array[i]+array[j]
if temp in map and map[temp] > 0:
map[temp] -= 1
for i in range(n):
key = array[i]
if key in map and map[key] == 0:
result[i] = true
return result