一、题目描述

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

你可以假设每种输入只会对应一个答案，并且你不能使用同一个元素两次。你可以按任意顺序返回答案。

示例1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums [0] + nums [1] = 2 + 7 = 9，所以返回 [0, 1]。

示例2：

输入：nums = [3,2,4], target = 6

输出：[1,2]

示例3：

输入：nums = [3,3], target = 6

输出：[0,1]

二、解答：

解法一：暴力枚举

1. 思路分析

暴力枚举的核心逻辑是双层循环遍历数组：

• 外层循环遍历每个元素，作为第一个候选数；
• 内层循环遍历当前元素之后的所有元素，作为第二个候选数；
• 检查两个数的和是否等于目标值，若满足则直接返回下标。

2.完整代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        # 外层循环：遍历每个元素作为第一个数
        for i in range(n - 1):
            # 内层循环：遍历当前元素之后的所有元素作为第二个数（避免重复检查）
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        # 题目保证有解，此处仅为语法完整性
        return []

3. 复杂度分析

• 时间复杂度：O()，n 是数组长度，双层循环最多执行 次。
• 空间复杂度：O(1)，仅使用了常数级别的额外空间。

4. 优缺点

• 优点：逻辑简单、容易理解，无需额外数据结构，适合算法新手入门。
• 缺点：时间效率低，当数组长度较大时（如 n > ），会出现明显的性能瓶颈。

解法二：哈希表

1. 思路分析

暴力解的核心问题是重复查找 “补数”（即 target - 当前数），哈希表（字典）可以将 “查找补数” 的操作从 O(n) 优化到 O(1)：

• 遍历数组时，用哈希表存储 “已遍历元素的值：下标”；
• 对当前元素，计算需要的补数 target - value；
• 若补数存在于哈希表中，说明之前遍历过该数，直接返回两者下标；
• 若不存在，将当前元素的值和下标存入哈希表，继续遍历。

2.完整代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 哈希表：存储已遍历元素的「值: 下标」
        mapping = {}
        # 遍历数组，同时获取下标和值
        for index, value in enumerate(nums):
            # 计算当前元素需要的补数
            complement = target - value
            # 检查补数是否在哈希表中（即是否已遍历过）
            if complement in mapping:
                # 若存在，返回补数的下标和当前下标
                return [mapping[complement], index]
            # 若不存在，将当前元素存入哈希表（先查后存，避免使用同一个元素）
            mapping[value] = index
        # 题目保证有解，此处仅为语法完整性
        return []

3. 复杂度分析

• 时间复杂度：O(n)，仅需遍历数组一次，每次哈希表的查找 / 插入操作都是 O(1)。
• 空间复杂度：O(n)，最坏情况下需要存储数组中所有元素（除了最后一个）。

4. 优缺点

• 优点：时间效率最优，是 LeetCode 官方推荐的最优解法。
• 缺点：需要额外的哈希表空间，逻辑比暴力解稍复杂，但理解后极易掌握。