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

Question

我们有 set/array M 个实数。如果 M 中有 s 和 t，则 M 中的数 r 是组成的 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

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

Function on an array of real numbers that finds out if number in the array is composed for every number in array

arrays

algorithm

pseudocode