【每日一题】01

题目描述

问题： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个数，并返回它们的数组下标。

示例：输入: nums = [2, 7, 11, 15], target = 9 输出: [0, 1] 解释: 因为 nums[0] + nums[1] == 9 (2 + 7)

输入输出格式

• 输入: 一个整数数组 nums 和一个整数 target。
• 输出: 一个包含两个整数的数组，表示满足 nums[i] + nums[j] == target 的下标 i 和 j。其中 i < j。

算法逻辑

1. 创建一个哈希表 hash_map 来存储已经遍历过的数字及其对应的索引。
2. 遍历数组 nums，对于每个元素 num：
   • 计算差值 complement = target - num。
   • 检查 complement 是否存在于 hash_map 中：
     • 如果存在，返回 hash_map[complement] 和当前索引 i。
     • 如果不存在，将 num 和当前索引 i 存入 hash_map。
3. 如果遍历结束后没有找到满足条件的两个数，则返回空数组。

代码实现

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return []

# 示例
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # 输出: [0, 1]

流程图

+-------------------+       +-------------------+
|  初始化哈希表     |       |  遍历数组 nums    |
+-------------------+       +-------------------+
           |                      |
           V                      V
+-------------------+       +-------------------+
|  计算差值 complement |       |  检查 complement 是否在哈希表中 |
+-------------------+       +-------------------+
           |                      |
           +----- 是 -----+       |
           |                      | 否
           V                      V
+-------------------+       +-------------------+
| 返回索引 [hash_map[complement], i] |       |  将 num 和 i 存入哈希表 |
+-------------------+       +-------------------+
           |                      |
           +----- 否 -----+       |
           |                      |
           V                      V
+-------------------+       +-------------------+
|  继续遍历            |       |  结束遍历，返回空数组 |
+-------------------+       +-------------------+

这个流程图以文本形式展示了算法的逻辑流程，从初始化哈希表开始，到遍历数组，计算差值，检查差值是否存在于哈希表中，然后根据情况返回结果或者继续遍历。

总结

这个题目是一个经典的算法问题，考察了哈希表的应用。希望这个详细的题目描述、逻辑解释、代码实现和流程图能帮助你更好地理解和掌握这个问题。