0001. 两数之和 #

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

题目大意 #

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

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

解题思路 #

思路 1：枚举算法 #

最简单的思路是枚举算法。使用两重循环枚举数组中每一个数 nums[i]、nums[j]。判断所有的 nums[i] + nums[j] 是否等于 target。

如果出现 nums[i] + nums[j] == target，则说明数组中存在和为 target 的两个整数，将两个整数的下标 i、j 输出即可。

利用两重循环进行枚举的时间复杂度为 $O(n^2)$。

思路 2：哈希表 #

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

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

利用哈希表求解的时间复杂度为 $O(n)$。

代码 #

思路 1 代码： #

1
2
3
4
5
6
7


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if i != j and nums[i] + nums[j] == target:
                    return [i, j]
        return []

思路 2 代码： #

1
2
3
4
5
6
7


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]