输入n个整数,找出其中的两个数,它们之和等于整个数m
时间: 2024-09-28 11:05:54 浏览: 31
输入两个正整数m和n求其最大公约数和最小公倍数 (2).pdf
这是一个经典的算法问题,通常被称为“两数之和”(Two Sum)。给定一个整数数组 `nums` 和一个目标值 `m`,你需要找到数组中是否存在两个不同的元素,使得它们相加的结果等于 `m`。这个问题可以使用哈希表(Hash Table)或者双指针(Two Pointers)技巧来解决。
解决方案步骤如下:
1. 创建一个空的哈希表(或字典)用于存储每个元素及其索引。
2. 遍历输入数组 `nums` 的每一个元素(从第一个开始),对于每个元素 `num`:
a. 检查哈希表中是否存在 `m - num` 的键。如果存在,说明找到了一对和为目标值的数,返回这两个元素的索引。
b. 如果不存在,将当前元素 `num` 作为键添加到哈希表中,并更新其对应的值为当前索引。
3. 如果遍历完整个数组都没有找到合适的数对,就表示数组中没有满足条件的元素。
```python
def twoSum(nums, m):
hash_table = {}
for i, num in enumerate(nums):
if m - num in hash_table:
return [hash_table[m - num], i]
hash_table[num] = i
return None
# 示例
nums = [2, 7, 11, 15]
m = 9
print(twoSum(nums, m)) # 输出:[0, 1]
```
阅读全文