LeetCode刷题笔记(1)—— 两数之和

简介: LeetCode刷题笔记(1)—— 两数之和

一、题目描述:

  • 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
  • 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
  • 你可以按任意顺序返回答案。


示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

提示:

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


二、题解:

解法一:朴素解法

def find(nums, target):
    length = len(nums)
    j = -1
    for i in range(length):
        if (target - nums[i]) in nums:
            if (nums.count(target - nums[i]) == 1) & (target - nums[i] == nums[i]):
                continue
            else:
                j = nums.index(target - nums[i], i + 1)
                break
    if j > 0:
        return [i, j]
    else:
        return []


def main():
    nums = list(map(int, input("请输入nums(整数数组):").strip().split()))
    n = int(input("请输入target(整数目标值):"))
    print(find(nums, n))


main()

注:对于nums = list(map(int, input("请输入nums(整数数组):").strip().split())),指先删除输入的字符串头尾的空格,然后以空格或者制表符为分隔符。map()在Python 3.x中返回的是迭代器,所以Python 3.x要加list()函数将迭代器转化为列表。


对于list(map(int, input().strip().split()))的补充知识:
  • 1、map函数用法
  • 描述:map() 函数会根据提供的函数对指定序列做映射。
  • 第一个参数 function 以参数序列中的每一个元素调用 function 函数,返回包含每次 function 函数返回值的新列表。
  • 语法:map(function, iterable, …)
  • 参数:function – 函数
  • iterable – 一个或多个序列
  • 返回值:返回一个迭代器。
  • 举例:
def square(x):  # 计算平方数
    return x ** 2


print(map(square, [1, 2, 3, 4, 5]))  # 计算列表各个元素的平方
# <map object at 0x100d3d550>     # 返回迭代器
print(list(map(square, [1, 2, 3, 4, 5])))  # 使用 list() 转换为列表
# [1, 4, 9, 16, 25]
print(list(map(lambda x: x ** 2, [1, 2, 3, 4, 5])))  # 使用 lambda 匿名函数
# [1, 4, 9, 16, 25]
2、 strip()方法:
  • 描述:Python strip() 方法用于移除字符串头尾指定的字符(默认为空格)或字符序列。
    注意:该方法只能删除开头或是结尾的字符,不能删除中间部分的字符。
  • 语法:str.strip([chars]);
  • 补充:
    s.strip(rm) 删除s字符串中开头、结尾处,位于 rm删除序列的字符
    s.lstrip(rm) 删除s字符串中开头处,位于 rm删除序列的字符
    s.rstrip(rm) 删除s字符串中结尾处,位于 rm删除序列的字符
  • 参数:chars – 移除字符串头尾指定的字符序列。
  • 返回值:返回移除字符串头尾指定的字符序列生成的新字符串
  • 示例:
str = "*****this is **string** example....wow!!!*****"
print(str.strip('*'))  # 指定字符串 *
# 输出:
# this is **string** example....wow!!!
3、split()方法
  • 描述:split() 通过指定分隔符对字符串进行切片,如果第二个参数 num 有指定值,则分割为 num+1 个子字符串。
  • 语法:str.split(str="", num=string.count(str))
  • 参数:str – 分隔符,默认为所有的空字符,包括空格、换行(\n)、制表符(\t)等。
    num – 分割次数。默认为 -1, 即分隔所有。
  • 返回值:返回分割后的字符串列表
  • 举例:
str = "this is string example....wow!!!"
print(str.split())  # 以空格为分隔符
print(str.split('i', 1))  # 以 i 为分隔符
print(str.split('w'))  # 以 w 为分隔符
# 输出:
# ['this', 'is', 'string', 'example....wow!!!']
# ['th', 's is string example....wow!!!']
# ['this is string example....', 'o', '!!!']
# 亲测str.split()和str.split( )输出结果无区别。

解法二:对解法一的优化

def find(nums, target):
    lens = len(nums)
    j = -1
    for i in range(1, lens):
        temp = nums[:i]
        if (target - nums[i]) in temp:
            j = temp.index(target - nums[i])
            break
    if j >= 0:
        return [j, i]


def main():
    nums = list(map(int, input("请输入nums(整数数组):").strip().split()))
    n = int(input("请输入target(整数目标值):"))
    print(find(nums, n))


main()

注:这里优化了解法一的代码,num2 的查找并不需要每次从 nums 查找一遍,只需要从 num1 位置之前或之后查找即可。为了方便, index 这里选择从 num1 位置之前查找。

对于 temp = nums[:i]的补充知识:
  • 1、切片:、
  • 一个完整的切片表达式包含两个“:”,用于分隔三个参数(start_index、end_index、step),当只有一个“:”时,默认第三个参数step=1。
  • 切片操作基本表达式:object[start_index : end_index : step]
  • step:正负数均可,其绝对值大小决定了切取数据时的“步长”,而正负号决定了“切取方向”,正表示“从左往右”取值,负表示“从右往左”取值。当step省略时,默认为1,即从左往右以增量1取值。“切取方向非常重要!
  • start_index:表示起始索引(包含该索引本身);该参数省略时,表示从对象“端点”开始取值,至于是从“起点”还是从“终点”开始,则由step参数的正负决定,step为正从“起点”开始,为负从“终点”开始。
  • end_index:表示终止索引(不包含该索引本身);该参数省略时,表示一直取到数据”端点“,至于是到”起点“还是到”终点“,同样由step参数的正负决定,step为正时直到”终点“,为负时直到”起点“。

举例:

a =
2、range() 函数用法:
  • Python3 range() 函数返回的是一个可迭代对象(类型是对象),而不是列表类型, 所以打印的时候不会打印列表。
  • Python3 list() 函数是对象迭代器,可以把range()返回的可迭代对象转为一个列表,返回的变量类型为列表。
  • 语法:range(stop)
    range(start, stop[, step])
  • 参数说明:

start: 计数从 start 开始。默认是从 0 开始。例如range(5)等价于range(0, 5);

stop: 计数到 stop 结束,但不包括 stop。例如:range(0, 5) 是[0, 1, 2, 3, 4]没有5

step:步长,默认为1。例如:range(0, 5) 等价于 range(0, 5, 1)

解法三:字典来模拟哈希查询的过程求解(来自Leecode题解)

def t

注:第一个for循环的过程是模拟建立哈希表,第二个for循环是查询。

补充知识:
  • 1、Hash(哈希)
  • 介绍:Hash :散列,通过关于键值(key)的函数,将数据映射到内存存储中一个位置来访问。这个过程叫做Hash,这个映射函数称做散列函数,存放记录的数组称做散列表(Hash Table),又叫哈希表。它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。该数据结构可以理解为一个线性表,但是其中的元素不是紧密排列的,而是可能存在空隙。
  • Hash的优点:先分类再查找,通过计算缩小范围,加快查找速度。
  • 举例:对于集合:{13,19,25,27,17},
  • (1)若是采用数组或链表结构:
  • 访问其中的一个元素(如18),需要遍历整个集合的元素,时间复杂度为O(n)。
  • (2)而采用哈希表时:
  • 假如散列函数为H[key] = key % 5;则集合元素对应的hash值分别为{3,4,0,2,2}。
  • 访问元素(18)只需要在Hash值为2的集合中寻找即可.
  • 如果访问没有哈希冲突的元素,例如访问(25),可以直接访问哈希值为(0)的值。
  • 故hash时间复杂度最差(所有的数据都映射到了内存存储中的同一个位置)才为O(n),最优情况(没有冲突的时候)下只需要O(1);一个好的哈希函数(散列函数)的值应尽可能平均分布。
  • 由上面的例子,我们可以想象,如果由大量的数据,采用数组或是链表存储时,访问需要遍历,耗费的时间非常多,而Hash表通过哈希计算,可以直接定位到数据所在位置(发生哈希冲突时,哈希值相同,可以定位到较小范围)大大加快了 查找的速度,节省了大量时间。
2、enumerate() 函数
  • 描述:enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中。
  • 语法:enumerate(sequence, [start=0])
  • 参数:sequence – 一个序列、迭代器或其他支持迭代对象;start – 下标起始位置。
  • 返回值:返回 enumerate(枚举) 对象。
  • 示例:
sea

解法四:对解法三的优化(来自Leecode题解)

def twoSu

注:类似解法二,不需要 mun2 不需要在整个 dict 中去查找。可以在 num1 之前的 dict 中查找,因此就只需要一次循环可解决。

三、输出结果:

相关文章
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
17天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
16 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
1月前
|
C++
Leetcode第一题(两数之和)
这篇文章介绍了解决LeetCode第一题“两数之和”的两种方法:暴力法和哈希表法,并提供了相应的C++代码实现。
28 0
Leetcode第一题(两数之和)
|
1月前
|
存储 C++ 容器
【LeetCode 13】1.两数之和
【LeetCode 13】1.两数之和
14 0
|
3月前
|
存储 索引
LeetCode------两数之和(3)【数组】
这篇文章介绍了LeetCode上的"两数之和"问题,提供了两种解法:一种是暴力求解法,通过双层循环遍历数组元素对查找两数之和为目标值的索引,时间复杂度为O(n^2);另一种是使用HashMap优化,通过存储元素值和索引,时间复杂度降低到O(n)。
LeetCode------两数之和(3)【数组】
|
3月前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
26 1
|
3月前
|
算法
LeetCode第1题两数之和
该文章介绍了 LeetCode 第 1 题两数之和的解法,通过使用 HashMap 来记录数组元素及其下标,以 O(n)的时间复杂度解决问题。
|
3月前
|
JavaScript 前端开发 PHP
leetcode——两数之和【一】
leetcode——两数之和【一】
28 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
39 0