python给定一个整数数组 和一个整数目标值,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。 每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
时间: 2023-08-14 18:24:53 浏览: 110
好的,这是一道经典的算法题,可以使用哈希表来解决。具体思路如下:
1. 创建一个空哈希表,用于存储数组中的元素及其对应的下标。
2. 遍历数组中的每个元素,如果该元素的值在哈希表中出现过,则说明之前已经出现过与其相加等于目标值的元素,直接返回这两个元素的下标即可。
3. 如果该元素的值在哈希表中没有出现过,则将该元素的值和下标存入哈希表中。
4. 如果遍历完数组后仍然没有找到两个元素的和等于目标值,则说明该数组中不存在这样的两个元素,返回空列表即可。
下面是 Python 代码实现:
```python
def twoSum(nums, target):
# 创建一个空哈希表
hashmap = {}
# 遍历数组中的每个元素
for i in range(len(nums)):
# 如果该元素的值在哈希表中出现过,则说明之前已经出现过与其相加等于目标值的元素,直接返回这两个元素的下标即可
if target - nums[i] in hashmap:
return [hashmap[target - nums[i]], i]
# 如果该元素的值在哈希表中没有出现过,则将该元素的值和下标存入哈希表中
hashmap[nums[i]] = i
# 如果遍历完数组后仍然没有找到两个元素的和等于目标值,则说明该数组中不存在这样的两个元素,返回空列表即可
return []
```
以上代码时间复杂度为 O(n),空间复杂度为 O(n)。
阅读全文