algorithm - 构建哈希表或字典 - 复杂性

Question

刚遇到这个问题:

子集求和问题:求给定数组中两对数字的总和等于给定数字的个数

例如:给定总和为 9，数组为 { 0, 1, 2, 7, 13 } => O/P 为 1 对(2 和 7)

似乎这可以在 O(n) (构建哈希表或字典，迭代给定数组的每个元素并从给定的总和中减去, 检查结果数是否在数组中)

显然，遍历数组的每个元素需要 O(n) 时间。

我的问题是构建哈希表或字典的时间复杂度和空间复杂度是多少？

注意 1:我猜测构建哈希表或字典的时间复杂度为 O(n)，我们必须再次遍历数组中的每个元素。 这是正确的吗？

注意 2:那么，复杂度是 O(n) + O(n) = 2 * O(n) 对吗？ (但答案似乎只是 O(n))

Answer 1

时间复杂度应该是 O(n)，而不是 O(n) + O(n) = 2 * O(n)。

在哈希表中插入元素是常量操作，因此需要 O(1) 时间，而您在此处执行该操作 n 时间，因此它将是 O(n) * O(1)。

所以最终它将是 O(n)。

Data Structure with Time & Space Complexity.