新塘做网站公司,wordpress变成英文,东莞专业网站建设服务,对电子政务网站建设的建议文章目录 #x1f340;题目#x1f340;解法一#x1f340;解法二#x1f340;哈希表 #x1f340;题目 给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。 你可以假设每… 文章目录 题目解法一解法二哈希表 题目 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。 解法一
暴力解法最先想到的方法 但是在运行的时候出现了一个问题 for i in len(nums):for j in range(i1, len(nums)):if nums[i]nums[j]target:return [i,j]但是报错了还是本人基本语法掌握不好 经查阅后 错误消息TypeError: ‘int’ object is not iterable通常在Python中出现当您尝试像遍历循环可迭代对象一样遍历整数int值时比如列表、元组或字符串等时会出现此错误。在Python中您只能遍历支持迭代的对象如序列和集合。总的来看列表、字典、集合、元组、字符串可迭代整数、浮点数、布尔、NoneType不可迭代 修改后的代码如下
n len(nums)for i in range(n):for j in range(i1, n):if nums[i]nums[j]target:return [i,j]补充range(n) 创建的对象是一个类似于序列的可迭代对象但它实际上并不存储整个范围内的所有值而是根据需要生成这些值从而节省内存空间。这种懒加载lazy loading的方式使得 range 在处理大范围的整数时非常高效 解法二
思路及算法
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此我们需要一种更优秀的方法能够快速寻找数组中是否存在目标元素。如果存在我们需要找出它的索引。
使用哈希表可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N)O(N) 降低到 O(1)O(1)O(1)。
这样我们创建一个哈希表对于每一个 x我们首先查询哈希表中是否存在 target - x然后将 x 插入到哈希表中即可保证不会让 x 和自己匹配。
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:hashtable dict()for i, num in enumerate(nums):if target - num in hashtable:return [hashtable[target - num], i]hashtable[nums[i]] ireturn []官方给出的答案里有些函数和语句可能不太了解这里我说明一下 dict()是创建一个空字典 enumerate() 是一个内置函数用于在迭代过程中同时获取索引和元素值通常用于循环遍历列表、元组、字符串等可迭代对象时。其基本语法如下 hashtable[nums[i]] i 的作用是将列表中的元素作为键将其索引作为值存储到一个哈希表字典中。这个哈希表可以用来快速查找特定元素在列表中的索引因为字典的键是唯一的通过元素值可以直接定位到其索引。 iterable 是要枚举的可迭代对象如列表、元组、字符串等。 start 是可选参数表示索引起始值默认为0但你可以指定一个不同的起始值。 enumerate() 返回一个迭代器每次迭代都产生一个元组包含两个值索引和元素值。索引从指定的起始值开始递增。 哈希表 哈希表Hash Table也被称为散列表是一种常见的数据结构用于高效地存储和检索键值对key-value pairs。哈希表的核心思想是通过将键key映射到一个确定的位置索引来实现快速的数据访问。这个映射函数被称为哈希函数hash function。 以下是哈希表的主要特点和工作原理 快速查找 哈希表的主要优势在于它可以在平均情况下取决于哈希函数的质量和哈希表的实现方式提供常数时间复杂度的查找操作即O(1)时间复杂度。 哈希函数 哈希表的关键部分是哈希函数它将键映射到哈希表中的一个位置。好的哈希函数应该尽可能均匀地分布键以减少冲突多个键映射到同一位置的发生。冲突是哈希表需要解决的主要问题之一。 冲突解决 当两个不同的键经过哈希函数映射到同一位置时就发生了冲突。哈希表有多种方法来解决冲突包括链地址法Chaining、开放寻址法Open Addressing等。每种方法都有自己的优点和适用场景。 动态扩展 哈希表通常会动态扩展以处理更多的键值对。当表格装填因键值对的添加而变得过高时哈希表会重新调整大小以保持其性能。 无序性 哈希表是无序的数据结构键值对的顺序不一定与它们被添加到哈希表的顺序相同。 哈希表在计算机科学中有广泛的应用常见用途包括实现字典、集合、缓存等数据结构以及在数据库索引、哈希表查找等领域中的优化。哈希表的性能取决于哈希函数的质量和解决冲突的方法因此在设计和使用哈希表时需要注意选择合适的哈希函数和解决冲突的策略以确保其高效性和稳定性。 挑战与创造都是很痛苦的但是很充实。
