给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素
时间: 2023-10-20 20:08:37 浏览: 56
两数之和 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个
好的,这是一道经典的算法题,可以使用哈希表(Hash Table)来解决。具体思路如下:
1. 创建一个空的哈希表,用来存储数组中的元素及其对应的下标。
2. 遍历数组中的每个元素,每次遍历时,先判断 target 与当前元素的差值是否已经存在于哈希表中。
3. 如果存在,则说明已经找到了符合条件的两个数,直接返回它们的下标。
4. 如果不存在,则将当前元素及其下标存入哈希表中,等待后续的查找。
5. 如果遍历完整个数组还没有找到符合条件的两个数,则说明不存在这样的数对,返回空数组或者抛出异常。
下面是使用 Python 代码实现的例子:
```python
def twoSum(nums, target):
hash_table = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_table:
return [hash_table[complement], i]
hash_table[num] = i
return []
# 示例:
nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target)) # 输出 [0, 1]
```
在上面的代码中,我们使用字典(Python 中的哈希表)来实现了哈希表的功能,用键来存储数组中的元素,用值来存储元素在数组中的下标。在遍历数组的过程中,如果当前元素的差值已经存在于哈希表中,就说明已经找到了符合条件的两个数,直接返回它们的下标即可。如果遍历完整个数组还没有找到符合条件的两个数,则说明不存在这样的数对,返回空数组即可。
阅读全文