【LeetCode刷题笔记（1）】【Python】【两数之和】【简单】

LeetCode: 两数之和

题目描述

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

• 输入：一个整数数组 nums 和一个整数目标值 target
• 输出：返回一个包含两个整数下标的数组

要求：

• 每种输入只会对应一个答案（题目保证仅存在一个答案 ? 找到一个解，即可返回结果）。
• 数组中同一个元素在答案里不能重复出现（特殊情况决定了代码逻辑，下面会详细说明）。
• 可以按任意顺序返回答案。

示例：

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

提示：

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 只会存在一个有效答案

解决方案：哈希表

【哈希表】是一种非常高效的数据结构，它通过哈希函数将键映射到值上。在哈希表中，每个键都对应一个值，可以通过键快速地访问到对应的值。哈希表的优点是查找速度快，因为可以通过哈希函数快速计算出对应键的值的位置。

在Python中，【字典】的查找、插入和删除操作都是基于哈希表实现的。当向字典中插入一个键-值对时，Python会使用哈希函数计算键的哈希值，并将键-值对存储在哈希表中对应的索引位置上。当需要查找一个键对应的值时，Python会先使用哈希函数计算键的哈希值，然后在哈希表中查找对应的索引位置，从而获取到键对应的值。

在【两数之和】问题中，利用哈希表的解决步骤如下：

1. 定义哈希表来存储数组中每个元素及其索引，以便后续查找目标值。初始代码如下：

def twoSum(nums, target):  
    hash_map = {} # python字典是基于哈希表实现的
    for i, num in enumerate(nums):  
        hash_map[num] = i

2. 查找目标值与当前值的差是否存在于哈希表中，存在则返回它们的数组下标，终止循环；不存在则继续遍历；

• 目标值：题目的整数target；
• 当前值：利用for循环遍历整数数组 nums 时，当前遍历的元素值num；

根据题意，数组中同一个元素（指的是同一下标的元素）在答案里不能重复出现。因此，如果示例为：target = 6，nums = [3, 2, 4]，那么目标值和当前值的差值target - num = num是成立的 ==> 如果先将当前值num存储于哈希表hash_map中，然后判断目标值和当前值的差值target - num是否已存在哈希表中。那么，由于target - num = num 且当前值num已先一步存储于哈希表hash_map中，因此程序会输出[0, 0]，而不是预期结果[1, 2]。如下所示：

# 出错代码
class Solution:
    def twoSum(self, nums, target):  
        hash_map = {}  
        for i, num in enumerate(nums):  
            hash_map[num] = i  # 先将当前值num存储于哈希表hash_map中
            # 然后判断目标值和当前值的差值`target - num`是否已存在哈希表中
            complement = target - num  
            if complement in hash_map:  
                return [hash_map[complement], i]  

运行结果

因此，应该在当前值num存储于哈希表hash_map中之前，先判断target - num是否已存在哈希表中，代码如下：

class Solution:
    def twoSum(self, nums, target):  
        hash_map = {}  
        for i, num in enumerate(nums):  
        	# 先判断目标值和当前值的差值`target - num`是否已存在哈希表中
            complement = target - num  
            if complement in hash_map:  
                return [hash_map[complement], i]  
            # 再将当前值num存储于哈希表hash_map中，确保同一元素的索引不同重复出现在答案中
            hash_map[num] = i   

运行结果

复杂度分析

• 时间复杂度：O(N)，N是数组中的元素数量

  • 极端情况下，需要遍历整个数组 ===> O(N)
  • 每次循环，由于采用哈希表 ==> O(1) 地寻找 target - num

• 空间复杂度：O(N)

  • 极端情况下，哈希表需要存储N-1个键-值对(最后一个循环) ===> O(N)

结束语

• 亲爱的读者，感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见，因此在这里鼓励您对我们的博客进行评论。
• 您的建议和看法对我们来说非常重要，这有助于我们更好地了解您的需求，并提供更高质量的内容和服务。
• 无论您是喜欢我们的博客还是对其有任何疑问或建议，我们都非常期待您的留言。让我们一起互动，共同进步！谢谢您的支持和参与！
• 我会坚持不懈地创作，并持续优化博文质量，为您提供更好的阅读体验。
• 谢谢您的阅读！