[ LeetCode ] 题刷刷(Python)-第1题:两数之和

题目描述

给定一个整数数组 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]

解题

1.解法一:暴力破解,两for走天下

思路

遍历寻找当前num后与target - num相等的目标元素,返回当前num的下标和目标元素的下标

算法复杂度

时间复杂度:O(n^2),其中 n 是输入数组 nums 的长度。

代码中存在一个外层循环,其循环次数为 n,内层循环也是遍历从当前外层循环索引 i+1 开始的剩余元素,最坏情况下需要遍历 n-1 次。因此,在整体上,循环会进行 n*(n-1)/2 次比较,简化后仍为 O(n^2)。

空间复杂度:O(1)

因为它只使用了常数个额外空间来存储变量 results 和循环中的临时变量 index 和 j。

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

2.解法二:哈希表来咯

思路

初始化一个空字典 hashtable。
使用 enumerate 函数遍历 nums 列表,这样可以同时获得元素的值 num 和对应的下标 i。
对于每一个 num,检查 target - num 是否已经在 hashtable 中。如果存在,则说明找到了一对和为目标值的数,返回它们的下标 [hashtable[target - num], i]。
若当前 num 的值不在哈希表中,将其作为键存入哈希表,并将下标 i 作为对应的值。
如果循环结束都没有找到满足条件的数对,则返回一个空列表 [ ]。

算法复杂度

时间复杂度:O(n),其中 n 代表数组 nums 的长度。

该算法主要包含一个遍历数组的操作,即遍历整个输入数组 nums,并对每个元素执行一次查找操作。查找操作在哈希表中进行,由于哈希表的查找、插入操作在平均情况下均具有 O(1) 的时间复杂度,所以整个算法的时间复杂度主要取决于遍历数组的时间。

空间复杂度:O(n),其中n代表数组 nums 的长度。主要为哈希表的开销。

def twoSum(nums, target):hashtable = {}  for i, num in enumerate(nums):complement = target - numif complement in hashtable:return [hashtable[complement], i]hashtable[num] = i  return []

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/302215.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

深入了解iOS内存(WWDC 2018)笔记-内存诊断

主要记录下用于分析iOS/macOS 内存问题的笔记。 主要分析命令: vmmap, leaks, malloc_history 一:前言 有 3 种思考方式 你想看到对象的创建吗?你想要查看内存中引用对象或地址的内容吗?或者你只是想看看 一个实例有多大&#…

互联网大厂ssp面经之路:计算机网络part2

什么是 HTTP 和 HTTPS?它们之间有什么区别? a. HTTP(超文本传输协议)和HTTPS(安全超文本传输协议)是用于在Web上传输数据的协议。它们之间的区别在于安全性和数据传输方式。 b. HTTP是一种不安全的协议&…

【随笔】Git 高级篇 -- 整理提交记录(上)cherry-pick(十五)

💌 所属专栏:【Git】 😀 作  者:我是夜阑的狗🐶 🚀 个人简介:一个正在努力学技术的CV工程师,专注基础和实战分享 ,欢迎咨询! 💖 欢迎大…

加州大学欧文分校英语基础语法专项课程03:Simple Past Tense 学习笔记(完结)

Learn English: Beginning Grammar Specialization Specialization Certificate course 3: Simple Past Tense Course Certificate 本文是学习 https://www.coursera.org/learn/simple-past-tense 这门课的学习笔记,如有侵权,请联系删除。…

浙江大学李春阳团队Trends Plant Sci观点文章(IF=20):植物地下生态互作:为什么同性相斥,异性相吸?

在生态学中,人们一直致力于探究生物之间的相互作用,这些相互作用不仅包括物种之间的相互作用,还包括同一物种的不同性别之间的相互作用。对于异株植物物种来说,人们普遍认为异性之间的相互作用比同性之间的相互作用更弱&#xff0…

为说阿拉伯语的国家进行游戏本地化

阿拉伯语是由超过4亿人使用的语言,并且是二十多个国家的官方语言。进入这些国家的市场并非易事——虽然他们共享一种通用语言,但每个国家都有自己独特的文化,有自己的禁忌和对审查的处理方式。这就是为什么视频游戏公司长期以来都远离阿拉伯语…

Git如何将已经推送到服务器的文件夹“忽略”

例子:如果我们在推送之初,一股脑将工程的所有文件都备份,没有忽略 debug和release文件夹,反应过来想要将文件夹再次忽略,应该怎么操作呢? 如下解答方法: 1.在工程目录下新建文件 .gitignore …

graphicLayer.startDraw({指定type为curve曲线时,无法实现示例效果排查思路参考

graphicLayer.startDraw({指定type为curve曲线时,无法实现和示例一样的曲线效果的排查思路参考: 相关代码: graphicLayer.startDraw({type: "curve",style: {color: "#ff0000",width: 3,},}); 相关效果: …

创建型模式--4.抽象工厂模式【弗兰奇一家】

1. 奔向大海 在海贼世界中,位于水之都的弗兰奇一家是由铁人弗兰奇所领导的以拆船为职业的家族,当然了他们的逆向工程做的也很好,会拆船必然会造船。船是海贼们出海所必备的海上交通工具,它由很多的零件组成,从宏观上看…

Mathpix和Simpletex对比

原始资料 Mathpix结果 已知集合 A { y ∣ y 2 x } , B { x ∣ x ≥ a } A\left\{y \mid y2^{\sqrt{x}}\right\}, B\{x \mid x \geq a\} A{y∣y2x ​},B{x∣x≥a}, 若 A B AB AB, 则 a a a 的值为 ( ) A. 1 B. 2 C. 3 D. 4复数 z a i ( a ∈ R , i za\mathrm{i} \qua…

React - 你知道useffect函数内如何模拟生命周期吗

难度级别:中级及以上 提问概率:65% 很多前端开发人员习惯了Vue或者React的组件式开发,熟知组件的周期过程包含初始化、挂载完成、修改和卸载等阶段。但是当使用Hooks做业务开发的时候,看见一个个useEffect函数,却显得有些迷茫,因为在us…

windows安装使用nacos

1.下载安装包 网址:Releases alibaba/nacos GitHub 2.解压,bin目录下修改启动脚本为单机 3.修改数据库配置,使用本地mysql数据库 3.1 创建nacos数据库 3.2 执行 nacos\conf 目录下数据库脚本 4.修改nacos\conf目录下数据库配置 5.点击运…

【数据结构】考研真题攻克与重点知识点剖析 - 第 5 篇:树与二叉树

前言 本文基础知识部分来自于b站:分享笔记的好人儿的思维导图与王道考研课程,感谢大佬的开源精神,习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析,本人技术…

Javascript进阶内容

1. 作用域 1.1 局部作用域 局部作用域分为函数作用域 和 块级作用域 块级作用域就是用 {} 包起来的,let、const声明的变量就是产生块作用域,var不会;不同代码块之间的变量无法互相访问,里面的变量外部无法访问 1.2 全局作用域…

【图论】Leetcode 994. 腐烂的橘子【中等】

腐烂的橘子 在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一: 值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。 每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单…

Redis在windows中安装启动停止

Redis下载 Redis安装 解压即可 启动 停止 ctrlc 启动客户机 设置密码 打开redis.windows.conf Spring Data Redis 使用方式 导入spring Data Redis 的maven坐标 配置Redis数据源 3编写编写配置类,创建RedisTemplate对象

day75 js 正则表达式 window对象轮播图片调用定时器

一 正则表达式: RegExp 对象: 对字符串执行模式匹配的强大工具。 1 创建正则表达式对象 let reg /模式/修饰符 修饰符 attributes 是一个可选的字符串,包含属性 "g"、"i" 和 "m", …

信息泄露漏洞的JS整改方案

引言 🛡️ 日常工作中,我们经常会面临线上环境被第三方安全厂商扫描出JS信息泄露漏洞的情况,这给我们的系统安全带来了潜在威胁。但幸运的是,对于这类漏洞的整改并不复杂。本文将介绍几种可行的整改方法,以及其中一种…

操作系统理论知识快速总览

操作系统整体架构 搬出考研时的思维导图 操作系统主要分为 批处理系统(老古董,基本不用了)实时操作系统(嵌入式中使用较多,RTOS)分时操作系统(PC中使用较多,Linux,Windows) 分时操作系统和实时操作系统的使用场景不同&#xf…

pytest的时候输出一个F后面跟很多绿色的点解读

使用pytest来测试pyramid和kotti项目,在kotti项目测试的时候,输出一个F后面跟很多绿色的点,是什么意思呢? 原来在使用pytest进行测试时,输出中的“F”代表一个失败的测试(Failed),而…