两个数字的总和：为什么没有人这样做

Question

我正在寻找“双数和问题”的解决方案，我看到每个人都使用两个 for 循环我看到的另一种方法是使用哈希 table

 def twoSumHashing(num_arr, pair_sum):
    sums = []
    hashTable = {}

    for i in range(len(num_arr)):
        complement = pair_sum - num_arr[i]
        if complement in hashTable:
            print("Pair with sum", pair_sum,"is: (", num_arr[i],",",complement,")")
        hashTable[num_arr[i]] = num_arr[i]

# Driver Code
num_arr = [4, 5, 1, 8]
pair_sum = 9    
  
# Calling function
twoSumHashing(num_arr, pair_sum)

但是为什么没有人讨论这个解决方案

def two_num_sum(array, target):
    for num in array:
        match = target - num
        if match in array:
            return [match, num]
                 
    return "no result found"

使用散列 table 时，我们必须将值存储到散列 table 中。但这里没有必要。 1）这会影响解决方案的时间复杂度吗？ 2) 与数组相比，在散列 table 中查找一个值很容易，但是如果值的数量很大，将它们存储在散列中 table 需要更多 space 吗？

Answer 1

第一个函数

使用 O(n) 时间复杂度 遍历数组中的 n 个成员使用 O(n) space complexity 因为你可以有一对是第一个和最后一个，那么在最坏的情况下你可以存储最多 n-1 个数字。

第二个函数

使用 O(n^2) 时间复杂度 当你首先在数组上迭代然后使用 in 它使用__contains__ 在列表中，在最坏的情况下是 O(n)。所以第二个函数就像做两个循环来暴力解决方案。

在第二个函数中要指出的另一件事是，您不会 return 所有对，而只是找到的第一对。然后你可以尝试通过从 num+1 的索引迭代来修复它，但是你会有重复项。

这一切都归结为更重要的偏好 - 时间复杂度或 space 复杂度 -

这是众多面试/面试准备问题之一，您需要解释为什么您会使用功能二（如果工作正常）而不是功能一，反之亦然。

您的问题的答案

1.when using a hash table we have to store values into the hash table. But here there is no need for that. 1)Does that affect the time complexity of the solution?

是的，现在时间复杂度是 O(n^2)，这更糟

2)looking up a value in hash table is easy compared to array, but if the values are huge in number, does storing them in a hash table take more space?

在计算机中，数字只是位的表示。更大的数字可以占用更多 space，因为它们需要更多位来表示它们，但无论您存储在哪里，存储它们都是相同的。

Answer 2

首先，您作为解决方案提供的第二个函数不正确，没有return完整的答案列表。

其次，作为 Pythonist，最好说 dictionary 而不是 hash table。 python 字典是散列 table.

的实现之一

总之，关于您提出的其他问题：

使用两个 for 循环 是一种蛮力方法，实际上通常不是优化方法。字典比 python 中的列表快得多。所以为了时间复杂度，当然，字典是赢家。
从space复杂度的角度来看，使用字典肯定需要更多的内存分配，但以目前的硬件，这不是数十亿数字的本质问题。这取决于你的情况，速度对你来说是关键还是内存量。

两个数字的总和：为什么没有人这样做

Two number sum : why don't anybody do it this way

python

numbers

sum