fg电子游艺

1.两数之和

fg游乐电子官方网站

一,主题

给定一个整数nums数组和一个目标值target,找到数组中作为目标值的两个整数并返回它们的数组下标。

您可以假设每个输入仅对应一个答案。但是,您不能在此数组中重用相同的元素。

例:

第二,回答

2.1方法1:暴力法

复杂性分析:

时间复杂度:O(n ^ 2),对于每个元素,我们尝试通过遍历数组的其余部分来找到它对应的目标元素,这将花费O(n)时间。因此,时间复杂度为O(n ^ 2)。

空间复杂度:O(1)。

2.2方法2:双通哈希表

为了优化运行时复杂性,我们需要一种更有效的方法来检查数组中是否存在目标元素。如果它存在,我们需要找出它的索引。保持数组中每个元素对应于其索引的最佳方法是什么?哈希表。

通过交换空间以获得速度,我们可以将寻道时间从O(n)减少到O(1)。哈希表是为此目的而构建的,支持在大致恒定的时间快速查找。我使用“近似”来描述它,因为在发生冲突时,查找时间可能会退化为O(n)。但只要您仔细选择哈希函数,查找哈希表的时间应该分摊到O(1)。

一个简单的实现使用两次迭代。在第一次迭代中,我们将每个元素的值及其索引添加到表中。然后,在第二次迭代中,我们将检查表中是否存在与每个元素相对应的目标元素(target - nums [i])。请注意,目标元素不能是nums [i]本身!

复杂性分析:

时间复杂度:O(n),我们遍历包含n个元素的列表两次。由于哈希表将查找时间缩短为O(1),因此时间复杂度为O(n)。

空间复杂度:O(n),所需的额外空间取决于存储在哈希表中的元素的数量,哈希表存储n个元素。

2.3方法3:哈希表一次

事实证明,我们可以立刻完成所有工作。在迭代并将元素插入表中时,我们还将返回并检查表中是否已存在与当前元素对应的目标元素。如果存在,那么我们找到了相应的解决方案并立即返回。

复杂性分析:

时间复杂度:O(n),我们只遍历包含n个元素的列表一次。在表中进行的每次查找只需要O(1)时间。

空间复杂度:O(n),所需的额外空间取决于存储在哈希表中的元素数量,这需要存储多达n个元素。