给定一个目标数和数组,找出数组中满足两数之和等于目标数的两数及其下标 给定一个整数数组和一个目标值,在该数组中找出和为目标值的那两个整数,并返回数组下标。
时间: 2024-09-26 08:01:36 浏览: 6
这个问题是一个经典的“两数之和”(Two Sum)问题,通常用于评估算法性能和数据结构的理解。在Python中,可以使用哈希表(字典)来解决这个问题,其时间复杂度为O(n)。以下是基本的解题思路:
1. 遍历数组(从第一个元素开始),对于每一个元素nums[i]:
- 计算目标值target - nums[i],这个新值代表我们需要找到的另一个数的值。
- 检查是否在之前遍历过的元素中找到了匹配的数,即字典中是否存在目标值target - nums[i]。如果存在,说明当前元素与之前找到的那个元素相加等于目标值,直接返回这两个元素的索引[i]和之前找到的索引。
- 将当前元素及其索引i添加到字典中,作为键值对(nums[i]: i),以便后续查找。
以下是具体的Python代码实现:
```python
def two_sum(nums, target):
if len(nums) < 2:
return "数组长度小于2"
hash_table = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_table:
return [hash_table[complement], i]
else:
hash_table[num] = i
return "没有找到满足条件的两数之和"
# 示例
arr = [2, 7, 11, 15]
target = 9
print(two_sum(arr, target)) # 输出:[0, 1]
```
在这个例子中,数组`[2, 7, 11, 15]`中有两组数的和为9:2+7=9和1+8=9(8是11-3,而1是在遍历过程中找到的)。所以函数返回[0, 1]。