首页 > 其他分享 >力扣题解1-两数之和

力扣题解1-两数之和

时间:2024-07-26 15:18:46浏览次数:9  
标签:index hash 题解 力扣 索引 num 哈希 table 两数

LeetCode 第一题 "两数之和" (Two Sum) 问题

分析过程:

这个问题可以通过多种方法解决,包括暴力解法和使用哈希表的解法。以下是详细的分析过程:

  1. 暴力解法

    • 遍历数组中的每一对元素,检查它们的和是否等于目标值。
    • 时间复杂度是 O(n^2),其中 n 是数组的长度。
  2. 使用哈希表

    • 使用一个哈希表来存储数组中的每个元素及其对应的索引。
    • 在遍历数组时,检查当前元素与目标值之差是否存在于哈希表中。
    • 如果存在,说明找到了两个元素,它们的和等于目标值。

哈希表解法的实现:

def two_sum(nums, target):
    # 创建一个哈希表(字典)来存储数组中的每个元素及其对应的索引
    num_to_index = {}
    
    # 遍历数组
    for index, num in enumerate(nums):
        # 计算当前元素与目标值之差
        complement = target - num
        
        # 检查差值是否存在于哈希表中
        if complement in num_to_index:
            # 如果存在,返回当前元素的索引和差值对应的索引
            return [num_to_index[complement], index]
        
        # 将当前元素及其索引存入哈希表
        num_to_index[num] = index

    # 如果没有找到符合条件的两个元素,返回空列表
    return []

# 示例
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # 输出:[0, 1]

详细步骤:

  1. 初始化一个空的哈希表 num_to_index
  2. 遍历数组 nums,对于每个元素 num 及其索引 index
    • 计算 complement = target - num
    • 检查 complement 是否在哈希表 num_to_index 中:
      • 如果在,返回 [num_to_index[complement], index]
      • 如果不在,将 num 及其 index 存入哈希表 num_to_index
  3. 如果遍历结束后仍未找到符合条件的元素对,返回空列表。

这种方法的时间复杂度是 O(n),空间复杂度也是 O(n),比暴力解法更高效。

哈希表的基本概念:

哈希表(Hash Table)是一种高效的数据结构,主要用于快速查找、插入和删除操作。哈希表使用键-值对(key-value pairs)来存储数据,通过一个称为哈希函数(hash function)的函数将键映射到表中的一个位置(数组的索引)。这种映射使得查找和插入操作的平均时间复杂度接近于 O(1)。

  1. 哈希函数(Hash Function)

    • 哈希函数将输入的键转换为数组的索引。
    • 一个好的哈希函数应当能将键均匀地分布到哈希表中,以减少冲突。
  2. 冲突(Collision)

    • 当两个不同的键被哈希函数映射到相同的索引时,称为冲突。
    • 解决冲突的方法有多种,包括链地址法(Separate Chaining)和开放地址法(Open Addressing)。
  3. 负载因子(Load Factor)

    • 负载因子是哈希表中已用槽的比例,计算方法是 已存储元素个数 / 哈希表的总槽数
    • 负载因子过高时,冲突增多,性能下降;负载因子过低时,空间浪费。

哈希表的实现方法:

  1. 链地址法(Separate Chaining)

    • 每个哈希表的槽(bucket)都是一个链表。
    • 当冲突发生时,新的元素被插入到链表的末尾。
    • 查找时,需要遍历该链表以找到目标元素。
    • 在 Python 中,字典(dict)和集合(set)的实现中使用了链地址法。
    # 链地址法示例
    hash_table = [[] for _ in range(10)]  # 创建一个包含10个槽的哈希表,每个槽是一个空列表
    
    def insert(hash_table, key, value):
        index = hash(key) % len(hash_table)
        hash_table[index].append((key, value))
    
    def get(hash_table, key):
        index = hash(key) % len(hash_table)
        for k, v in hash_table[index]:
            if k == key:
                return v
        return None
    
    # 插入和查找示例
    insert(hash_table, 'apple', 1)
    insert(hash_table, 'banana', 2)
    print(get(hash_table, 'apple'))  # 输出: 1
    print(get(hash_table, 'banana'))  # 输出: 2
    
  2. 开放地址法(Open Addressing)

    • 当冲突发生时,使用探测(probing)的方法在哈希表中寻找下一个可用槽。
    • 常见的探测方法有线性探测(Linear Probing)、二次探测(Quadratic Probing)和双重散列(Double Hashing)。
    # 开放地址法示例(线性探测)
    hash_table = [None] * 10  # 创建一个包含10个槽的哈希表
    
    def insert(hash_table, key, value):
        index = hash(key) % len(hash_table)
        while hash_table[index] is not None:
            index = (index + 1) % len(hash_table)
        hash_table[index] = (key, value)
    
    def get(hash_table, key):
        index = hash(key) % len(hash_table)
        while hash_table[index] is not None:
            k, v = hash_table[index]
            if k == key:
                return v
            index = (index + 1) % len(hash_table)
        return None
    
    # 插入和查找示例
    insert(hash_table, 'apple', 1)
    insert(hash_table, 'banana', 2)
    print(get(hash_table, 'apple'))  # 输出: 1
    print(get(hash_table, 'banana'))  # 输出: 2
    

哈希表的优缺点:

优点

  • 快速的查找、插入和删除操作,平均时间复杂度为 O(1)。
  • 适用于需要频繁查找操作的数据场景。

缺点

  • 需要一个好的哈希函数来减少冲突。
  • 哈希表的性能在最坏情况下(所有键都冲突)可能退化到 O(n)。
  • 哈希表需要更多的内存来存储空槽和解决冲突的数据结构。

Python 中的哈希表:

在 Python 中,字典(dict)和集合(set)都是通过哈希表来实现的。它们提供了快速的查找、插入和删除操作,非常适合需要高效数据存取的场景。

# 字典示例
my_dict = {'apple': 1, 'banana': 2}
print(my_dict['apple'])  # 输出: 1
my_dict['cherry'] = 3  # 插入新元素
print(my_dict['cherry'])  # 输出: 3

# 集合示例
my_set = {'apple', 'banana'}
print('apple' in my_set)  # 输出: True
my_set.add('cherry')  # 插入新元素
print(my_set)  # 输出: {'cherry', 'banana', 'apple'}

'enumerate'函数

在前面 two_sum 函数的实现中,enumerate 用于遍历 nums 列表,同时获取每个元素的索引和值,这样就可以在哈希表中存储元素值及其对应的索引,并在查找时使用。

enumerate 是 Python 内置函数,用于遍历序列(如列表、元组或字符串)时获取元素及其对应的索引。它返回一个迭代器,每次迭代时生成一个包含两个元素的元组:当前元素的索引和值。这个函数通常在需要索引和元素值的场景中非常有用,比如在循环中。

语法:

enumerate(iterable, start=0)
  • iterable:一个可以迭代的对象,比如列表、元组、字符串等。
  • start:可选参数,指定索引的起始值,默认从 0 开始。

示例:

# 示例列表
fruits = ['apple', 'banana', 'cherry']

# 使用 enumerate 获取索引和值
for index, fruit in enumerate(fruits):
    print(f"Index: {index}, Fruit: {fruit}")

输出:

Index: 0, Fruit: apple
Index: 1, Fruit: banana
Index: 2, Fruit: cherry

enumerate 的更多用法:

  1. 指定起始索引
    可以通过设置 start 参数来改变起始索引的值。

    for index, fruit in enumerate(fruits, start=1):
        print(f"Index: {index}, Fruit: {fruit}")
    

    输出:

    Index: 1, Fruit: apple
    Index: 2, Fruit: banana
    Index: 3, Fruit: cherry
    
  2. 与其他迭代器结合
    enumerate 可以与其他迭代器结合使用,例如列表生成器、集合等。

    fruits_set = {'apple', 'banana', 'cherry'}
    for index, fruit in enumerate(fruits_set):
        print(f"Index: {index}, Fruit: {fruit}")
    

    输出的顺序可能与输入顺序不同,因为集合是无序的。

标签:index,hash,题解,力扣,索引,num,哈希,table,两数
From: https://www.cnblogs.com/yukihan/p/18325442

相关文章

  • Pag动画:umi+libpag+copy-webpack-plugin实现及问题解决
    1、package.json添加如下,安装依赖:"libpag":"^4.2.84","copy-webpack-plugin":"9.1.0",为什么是写死的旧版本,后面解释2、使用的方法,这里只是一个小示例,具体如何使用看个人(这里主要是想记录过程中出现的问题及解决方式): constinit=async()=>{   constPag......
  • 优美子数列2 题解
    题目id:8628题目描述数学家小\(Q\)得到了一个长度为\(N\)的数列\(a_n\)。小\(Q\)的幸运数字是\(k\),所以他认为,若一个子数列\(a_l,a_{l+1},...,a_r\)的和为\(k\)的倍数,则该子数列是优美子数列。小\(Q\)现在想考考你,\(a_n\)里有多少个优美子数列呢?前置知识前缀和、桶解题思路......
  • 近期题解(2024.7.26)
    CF1070AFindaNumber一个朴素的想法是设\(dp_{x,y}\)表示模\(d\)为\(x\)且和为\(y\)的最小值,那么答案就是\(dp_{0,s}\)。自然初始状态为\(dp_{0,0}=0\),但是我们发现这个转移关系是带环的,所以说要把这个dp换成最短路。直接从\((0,0)\)为源跑一遍bfs即可,时间复......
  • 题解:Codeforces Round 961 (Div. 2) C
    C.Squaringtimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputikrpprppfoundanarray\(a\)consistingofintegers.Helikesjustice,sohewantstomake\(a\)fair —thatis,makeitnon......
  • 贪心算法(二) ------力扣860--柠檬水找零,力扣605--种花问题
    目录力扣860----柠檬水找零题目分析 代码 力扣605---种花问题问题题目分析 代码 力扣860----柠檬水找零题目在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。每位顾客只买一杯柠檬水,然后向你......
  • 魔术上网导致Github push 443 问题解决方法
    问题描述使用“kexue上网”工具后,在IDEA中push代码到github时,报错:Failedtoconnecttogithub.comport443:Operationtimedout。同时,使用浏览器访问github也会出现无法访问,偶尔能访问的情况。解决办法gitconfig--globalhttp.proxyhttp://127.0.0.1:1087git......
  • 【题解】「CSP模拟赛」雨天 rain
    雨天rain考场上打了一个动态开点线段树,但是被卡空间了......
  • 最小循环节——题解
    最小循环节题目链接题意简述我们需要找到一个字符\(s\)的最短的循环节,对循环节的定义为,当一个字符串\(t\)能够通过若干次自己加自己得到字符串\(s\),我们就称\(t\)是\(s\)的一个循环节。思路简述根据题意,字符串\(s\)本身就是自己的一个循环节。所以,当我们找不到更......
  • 使用React脚手架时npx速度慢的问题解决
    React作为目前最流行的前端框架之一,其开发效率和组件化特性受到了开发者的广泛欢迎。然而在使用React脚手架工具,如create-react-app进行项目初始化时,有时会遇到npx命令执行速度非常慢的问题。本文将探讨这一问题的原因,并提供一些有效的解决方案。问题分析npx是Node.js包管......
  • P9304 「DTOI-5」3-1题解,c++树的遍历例题
    题意给定以n(1≤n≤1......