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

力扣题解1-两数之和

时间：2024-07-26 15:18:46浏览次数：8  
标签：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......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99