No.1 Easy(有人相爱,有人夜 里开车看海,有人leetcode第一题都做不出来🤣)
- 解法1
🕚暴力枚举:从首部元素开始,依次开始向后遍历 target - x 的值即可。且元素x之前的元素已经和x匹配过,无需再次考虑。
时间复杂度:最坏的情况下是O(N的平方)
- 解法2
🚀哈希表:解法1当中的寻找 target - x 的过程导致方法的复杂度比较高,最高可遍历整个数组,所以使用哈希表,如果哈希表中存在target - nums[i],直接返回了;不存在的情况下,存入位置i的值。
扩展阅读
哈希表是一种数据结构,它提供了快速的插入、删除和查找操作。
- 哈希表使用哈希函数将键(Key)映射到桶(Bucket)中。如果两个键的哈希值相同,那么它们会被放入同一个桶中。
- 哈希表支持平均O(1)时间复杂度的查找、插入和删除操作。在最坏的情况下,这些操作的时间复杂度可能会增加到O(n),其中n是表中的元素数量。
- 哈希表通常使用链表或数组来处理哈希冲突。当两个或更多的键映射到同一个桶中时,就会发生哈希冲突。
- 哈希表的大小通常是固定的,这意味着如果哈希表变得太满(例如,负载因子超过了一定的阈值),就需要进行重新哈希以增加哈希表的大小。
- 哈希表不保持元素的插入顺序,也不能有效地进行排序操作。