LeetCode刷题---Two Sum(一)

简介: LeetCode刷题---Two Sum(一)

🍀题目

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。


🍀解法一

暴力解法,最先想到的方法

但是在运行的时候出现了一个问题

for i in len(nums):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j]==target:
                    return [i,j]

但是报错了(还是本人基本语法掌握不好)

经查阅后

错误消息"TypeError: ‘int’ object is not iterable"通常在Python中出现,当您尝试像遍历(循环)可迭代对象一样遍历整数(int)值时,比如列表、元组或字符串等时会出现此错误。在Python中,您只能遍历支持迭代的对象,如序列和集合。总的来看列表、字典、集合、元组、字符串可迭代;整数、浮点数、布尔、NoneType不可迭代

修改后的代码如下

n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i]+nums[j]==target:
                    return [i,j]

补充:range(n) 创建的对象是一个类似于序列的可迭代对象,但它实际上并不存储整个范围内的所有值,而是根据需要生成这些值,从而节省内存空间。这种懒加载(lazy loading)的方式使得 range 在处理大范围的整数时非常高效


🍀解法二

思路及算法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。

使用哈希表,可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N)O(N) 降低到 O(1)O(1)O(1)。

这样我们创建一个哈希表,对于每一个 x,我们首先查询哈希表中是否存在 target - x,然后将 x 插入到哈希表中,即可保证不会让 x 和自己匹配。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

官方给出的答案里,有些函数和语句可能不太了解,这里我说明一下

  • dict()是创建一个空字典
  • enumerate() 是一个内置函数,用于在迭代过程中同时获取索引和元素值,通常用于循环遍历列表、元组、字符串等可迭代对象时。其基本语法如下:
  • hashtable[nums[i]] = i 的作用是将列表中的元素作为键,将其索引作为值,存储到一个哈希表(字典)中。这个哈希表可以用来快速查找特定元素在列表中的索引,因为字典的键是唯一的,通过元素值可以直接定位到其索引。
    iterable 是要枚举的可迭代对象,如列表、元组、字符串等。
    start 是可选参数,表示索引起始值,默认为0,但你可以指定一个不同的起始值。
    enumerate() 返回一个迭代器,每次迭代都产生一个元组,包含两个值:索引和元素值。索引从指定的起始值开始递增。

🍀哈希表

哈希表(Hash Table),也被称为散列表,是一种常见的数据结构,用于高效地存储和检索键值对(key-value pairs)。哈希表的核心思想是通过将键(key)映射到一个确定的位置(索引)来实现快速的数据访问。这个映射函数被称为哈希函数(hash function)。

以下是哈希表的主要特点和工作原理:

  • 快速查找: 哈希表的主要优势在于它可以在平均情况下(取决于哈希函数的质量和哈希表的实现方式)提供常数时间复杂度的查找操作,即O(1)时间复杂度。
  • 哈希函数: 哈希表的关键部分是哈希函数,它将键映射到哈希表中的一个位置。好的哈希函数应该尽可能均匀地分布键,以减少冲突(多个键映射到同一位置)的发生。冲突是哈希表需要解决的主要问题之一。
  • 冲突解决: 当两个不同的键经过哈希函数映射到同一位置时,就发生了冲突。哈希表有多种方法来解决冲突,包括链地址法(Chaining)、开放寻址法(Open Addressing)等。每种方法都有自己的优点和适用场景。
  • 动态扩展: 哈希表通常会动态扩展,以处理更多的键值对。当表格装填因键值对的添加而变得过高时,哈希表会重新调整大小,以保持其性能。
  • 无序性: 哈希表是无序的数据结构,键值对的顺序不一定与它们被添加到哈希表的顺序相同。

哈希表在计算机科学中有广泛的应用,常见用途包括实现字典、集合、缓存等数据结构,以及在数据库索引、哈希表查找等领域中的优化。哈希表的性能取决于哈希函数的质量和解决冲突的方法,因此在设计和使用哈希表时,需要注意选择合适的哈希函数和解决冲突的策略,以确保其高效性和稳定性。


挑战与创造都是很痛苦的,但是很充实。


相关文章
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
1月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
1月前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
1月前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
1月前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
1月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
1月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串