0001. 两数之和.md

0001. 两数之和

• 标签：数组、哈希表
• 难度：简单

题目大意

描述：给定一个整数数组 nums 和一个整数目标值 target。

要求：在该数组中找出和为 target 的两个整数，并输出这两个整数的下标。

解题思路

最简单的思路是枚举数组中每一个数 nums[i]，寻找数组中是否存在 target - nums[i]。

这样利用两重循环暴力搜素，时间复杂度为 $O(n^2)$。

另一种思路是利用字典。字典中键值对信息为 target-nums[i] ：i。i 为下标。

遍历数组，对于每一个数 nums[i]，先查找字典中是否存在 target - nums[i]，存在则输出 target - nums[i] 对应的下标和当前数组的下标 i。没有则在字典中存入 target-nums[i] 的下标 i。

代码

def twoSum(self, nums: List[int], target: int) -> List[int]:
    numDict = dict()
    for i in range(len(nums)):
        if target-nums[i] in numDict:
            return numDict[target-nums[i]], i
        numDict[nums[i]] = i
    return [0]