0001. 两数之和

0001. 两数之和 #

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

题目大意 #

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

要求:在该数组中找出和为 target 的两个整数,并输出这两个整数的下标。可以按任意顺序返回答案。

说明

  • $2 \le nums.length \le 10^4$。
  • $-10^9 \le nums[i] \le 10^9$。
  • $-10^9 \le target \le 10^9$。
  • 只会存在一个有效答案。

示例

  • 示例 1:
1
2
3
输入nums = [2,7,11,15], target = 9
输出[0,1]
解释因为 nums[0] + nums[1] == 9 返回 [0, 1] 
  • 示例 2:
1
2
输入nums = [3,2,4], target = 6
输出[1,2]

解题思路 #

思路 1:枚举算法 #

  1. 使用两重循环枚举数组中每一个数 nums[i]nums[j],判断所有的 nums[i] + nums[j] 是否等于 target
  2. 如果出现 nums[i] + nums[j] == target,则说明数组中存在和为 target 的两个整数,将两个整数的下标 ij 输出即可。

思路 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 []

思路 1:复杂度分析 #

  • 时间复杂度:$O(n^2)$
  • 空间复杂度:$O(1)$。

思路 2:哈希表 #

哈希表中键值对信息为 target-nums[i] :ii 为下标。

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

思路 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]

思路 2:复杂度分析 #

  • 时间复杂度:$O(n)$,其中 $n$ 是数组 nums 的元素数量。
  • 空间复杂度:$O(n)$。
本站总访问量  次  |  您是本站第  位访问者