首页 > 编程语言 >Leetcode 1.两数之和 Python题解

Leetcode 1.两数之和 Python题解

时间:2023-04-23 15:59:36浏览次数:59  
标签:target nums Python 题解 复杂度 int result 两数 字典

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


1.暴力遍历法

解题思路:遍历数组,对于当前的元素 nums[i],如果 result=taget-nums[i] 在数组中,则返回这 nums[i]result 的下标。如果已经查询元素 nums[i] 的所有配对情况,且没有找到可以构成 target 的了一个元素,则下一次查询从第 i+1 个位置开始。

用到的知识

  1. python index方法:
    用法:nums.index(result)
    含义:获取resultnums列表中的下标

  2. python in关键字
    用法:result in nums
    含义:判断result是否在nums数组中
    时间复杂度:对列表使用in关键字的时间复杂度为O(n),对字典集合使用in关键字的时间复杂度为O(1)

解题代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            result=target-nums[i]
            if result in nums[i+1:]:
                return [i,nums[i+1:].index(result)+i+1]

复杂度分析

  1. 时间复杂度:O(n^2)
    Line-3循环3次,Line-5用in判断列表的时间复杂度为O(n),因此时间复杂度为O(n*n)=O(n^2)
  2. 空间复杂度:O(1)

2.哈希表

解题思路:为了降低时间复杂度,可以使用哈希表来进行判断。借助哈希表/字典,每次遍历列表,对于当前的元素nums[i],计算result=target-nums[i]是否存在于字典中。如果存在,则返回result的下标;如果不存在,则将{nums[i]:i}作为字典项存入字典中。使用字典有如下好处:①对字典使用in关键字的时间复杂度为O(1);②判断的同时可以获得result的下标。

解题代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_dict={}
        for i in range(len(nums)):
            result=target-nums[i]
            if result in hash_dict.keys():
                return [hash_dict[result],i]
            else:
                hash_dict[nums[i]]=i

复杂度分析

  1. 时间复杂度:O(n)
  2. 空间复杂度:O(n)

3.题目描述

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 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]

标签:target,nums,Python,题解,复杂度,int,result,两数,字典
From: https://www.cnblogs.com/venas/p/17346661.html

相关文章

  • python + informix+基本语句
    importjaydebeapiimportosimportloggingimporttimeclassPostgre_Person:def__init__(self):#打开数据库连接foriinrange(10):try:url=###user=###password=##......
  • 1 python操作哨兵 、2 python操作集群、3 缓存优化、4 mysql 主从 、5 django使用多数
    目录1python操作哨兵2python操作集群3缓存优化3.1redis缓存更新策略3.2缓存击穿,雪崩,穿透4mysql主从5django使用多数据库做读写分离1python操作哨兵#高可用架构后---》不能直接连某一个主库了---》主库可能会挂掉,后来它就不是主库了#之前学的连接redis的操作,就用不......
  • python 连接xiformix数据库
    importjaydebeapiforiinrange(10):try:url=######user=#####password=#####dirver='com.informix.jdbc.IfxDriver'jarFile="D:\\i......
  • 盘点一款Python发包收包利器——scapy
    今日鸡汤潮平两岸阔,风正一帆悬。    大家好,我是黄伟。今天跟大家讲的是Python用于发送接受网络数据包的模块-------scapy。前言众所周知,我们每天上网都会有很多数据包需要发送,然后处理在接受在发送,这样一个循环往复的过程,这里就显示了很多数据包的发送接收数据。那么,什么是包......
  • 第14届蓝桥杯C++B组省赛题解(更新中)
    目录A.日期统计题目内容思路代码答案B.01串的熵题目内容思路代码答案C.冶炼金属题目内容输入格式输出格式输入样例输出样例思路代码A.日期统计题目内容小蓝现在有一个长度为100的数组,数组中的每个元素的值都在0到9的范围之内。数组中的元素从左至右如下所示:5686......
  • 说说Python集合的那些事儿
    大家好,我是IT共享者,人称皮皮。今天给大家来捋一捋Python集合。一、什么是集合?集合(set)和字典(dict)类似,它是一组key的集合,但不存储value。集合的特性就是:key不能重复。二、集合常用操作1.创建集合set的创建可以使用{}也可以使用set函数:s1={'a','b','c','a','d','b'}......
  • Cmd输入python会打开 Windows 应用商店 解决方法
    当我在CMD中输入Python时,它会打开Windows应用商店让我下载Python3.7。这个问题今天无缘无故地开始了。我没有更改或下载有关Python的任何内容,并且已经尝试重新安装Python,并且Path环境变量是正确的。Answers使用Windows搜索栏查找“管理应用执行别名”。Pytho......
  • python matplotlib 散点图的拟合直线的简单示例
     #samplepointsX=[0,5,10,15,20]Y=[0,7,10,13,20]#solveforaandbdefbest_fit(X,Y):xbar=sum(X)/len(X)ybar=sum(Y)/len(Y)n=len(X)#orlen(Y)numer=sum([xi*yiforxi,yiinzip(X,Y)])-n*xbar*y......
  • Jmeter调用Python脚本实现参数互传(OS进程取样器)
    1:新增取样器--->os进程取样器--》配置命令、命令行参数;2.os进程取样器命令行地址下的bat文件的内容:  3.py文件接收jmeter传递过来的值: 4.正则提取os进程提取器返回的值,也就是py文件返回的值:  ......
  • redis高级-day6——python操作哨兵、python操作集群、缓存优化
    目录一、python操作哨兵二、python操作集群三、缓存优化3.1redis缓存更新策略3.2缓存击穿,雪崩,穿透一、python操作哨兵#高可用架构后---》不能直接连某一个主库了---》主库可能会挂掉,后来它就不是主库了#之前学的连接redis的操作,就用不了了importredisconn=redis.Red......