0001. 两数之和

0001. 两数之和 #

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

题目大意 #

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

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

解题思路 #

思路 1:枚举算法 #

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

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

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

思路 2:哈希表 #

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

  • 遍历数组,对于每一个数 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]
本站总访问量  次  |  您是本站第  位访问者