leetcode怎么刷hot100
hey， hello， 大家好，这里是蜜糖，一些小的算法技巧在咱们的工作和面试的过程中都是十分有用的，所以呢，我想做这么一期系列视频，就围绕着 lico 的这个编程网站上面的热题一百这个专栏来进行分模块的梳理和学习。 那这开门第一期呢，就围绕着哈西来进行，哈西是咱们开发过程中十分常见的核心机制之一啊。 那我理解哈西的本质就是通过一个有限的空间来映射一个无限的空间，再通过对这个有限空间内进行有序化，最终实现增速。 那有限空间应受无限空间必然会产生冲突，所以解决哈西冲突也是哈西的核心问题之一。但是在这里头，咱们就不对哈西的实现机制来进行过多的介绍，我们只聊一下他的应用。从应 用的层面上来说，我们对哈西的利用主要就是用它的提速啊，并且是空间换时间的提速。所以呢，在进行一些代码逻辑的优化的时候，我们就可以借助哈西来实现我们的目的，例如循环查库的时候，给他改成批量查询，最后再利用哈西来获取结果。 那好，咱们先来第一题啊，两数之和，给定一个整数数组和一个整数目标值，请你在该数组中找出来和为目标值的两个整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案，但是数组中的一个元素在答案中是不能重复出现的，你可以按任意的顺序返回答案。需要注意的是他后面的这四个提示啊，其中第一个数组的长度 是小于十的四次方大于二，其中数组中的数值是小于十的九次方，大于负十的九次方的这个目标值也是同样的。然后再次提示了只会存在一个有效答案， 因为第一题比较简单，所以咱们就针对这个提示展开的说一下。第一个提示说明了我们实际要处理的这个数据的量有多少，要知道我们在生产生活之中啊，需要估计实际业务中去处理的这个数据的实际数值 啊，数据量的大小会影响到咱们具体的方案选型。而在这个算法题中，一般来说扎瓦类的这个处理的数据规模都在十九次方左右，但是上下线会根据你单次的处理的场数的这个时间值 c 啊有关，那现在咱们这题的数据规模是十的四次方，也就意味着咱们最多是可以接受文方的这个答案解法。 那如果假设这个输入的是十了六次方呢，那这个欧文方他就超时了，因为这个在欧文方了之后，整体你就需要这个十二次方，十了十二次方的一个处理结果， 所以我们就可以通过提示来判断出我们至少要满足什么样的时间复杂度的方案才能够通过这个题目。那这第二第三个提示呢，都是针对输入和输出的数值来说的，输入和输出都要满足在正负十的九次方之间， 就是说这个数据规模的数据啊，我们是可以直接通过整数类型来进行加减的，我们都知道在 java 之中，这个整数类型的范围在负 的二的三十一次方和正的二的三十一次方减一之间大约为二幺四的乘车，一共十位，也就是说两个十九次方的数值直接相加之后还能再剩一点，那如果再多，我们就需要特别的使用长整形来进行数据结果的接收了。 所以呢，如果要是在面试之中你追求一次 ac 的话，那就要对这部分的题数来特别的留心啊，这个会影响你整体编程里头的面试得分的结果。 好，那咱们现在返回咱们题目的主干啊，结合提示可以知道，我们的目的是在输入的若干数字之中寻找两个求和等于目标值的这个数字，并返回下标。 那从这个直觉上啊，我们就是要说我们要干这么一件事的话，他要翻译成一段逻辑应该是什么样的呢？就是我们有两个步骤，第一步 步，因为咱们要覆盖所有的结果路径，所以是避免不了的，要去依次的便利所有的元素。那第二步呢，就是咱要针对已经选择了的元素去尝试找到啊，剩下的这些数字之中，到底是哪个和他去求和了之后，等于咱们的目标值， 根据这两步骤我们就可以看出来，第一步跳不了吗？是吧，因为他要保证咱们这个答案的准确性。那第二步的实验方式就是本题最终的这个优化点了，就是怎么能够快速的找到和目标值匹配的这个数字， 这两数之和作为刷题界里的 hello word 就是一般来说有两种解法吗？一种是暴力解，一种是哈西解，但实际上你要从这这两步就是上头，咱们说说这两步来说，他两个是一致的，只不过是说暴力解在 查找这个匹配的数字的时候就循环吗？再次便利，对，然后呢，哈西姐，对应的就是利用咱们这个本期里头的重点，这个哈西的数据结构来进行增速，所以呢，这两个结果实际上你可以用同一种逻辑框架来进行这个梳理。 那根据我们设置的这个两步骤，我们现在先完成第一个步骤啊，先创建一个外部循环，然后我们就可以是在执行我们的第二步骤，先选定一个数字 choice 取的就是这个 nam's i， 然后呢，我们已经有了一个 target 了，然后再有这个 choice， 我们就可以去计算这个 def 的这个的差值是 target 减去 choice， 那么我们接下来是 希望根据这个地府值来查询对应的这个值的位置，所以我们需要一个哈西卖铺来存储这个值，其中呢，第一个 integer 就是地府的这个值，第二个 integer 是地府的这个下标值。 接下来我们就要去判断过往的这个麦克里头是否存在当前的这个地步值，如果存在了的话，那就说明我们已经找到了这个数值了，那我们现在就返回。好，我们去拗一个呃，数组的一个对象， 其中第一个值是我们找到的这个 def 的下标，第二个是当前下标，那无论如果要是没找到的话，我们就继续处理，然后将当前的这个值去存储啊，当循环结束了之后， 我们就可以去返回了，接下来我们去看一眼执行结果 来测试一下， ok， 没问题啊，通过， ok， 接下来咱们第二题啊，四十九、字母意味词分组，给你一个词无串数组，请你将字母意味词组合在一起， 可以按任意的顺序返回结果列表其中给出来的定义。字母意味词是由重新排列原单词的所有字母之后得到的一个新的 单词，也就是说就是这几个单词字母差不多啊，相同，然后混合排列了之后，如果能够组成对方的话，那他俩就是互为这个字母意味词。 那接下来我们对这个题进一下分享。首先我们知道我们的目的就是要将所有的这个意味词都聚合到一起， 那还是两个步骤，第一个我们要便利所有的输入的字符串，第二个是判断已经处理的这些字符串之中是否存在跟当前咱们正在处理这个一样的，要是一样的话，那就给他去聚合，如果不一样的话，那就等待之后的处理。 那同样的第一步我们是绕不开的，我们必须要通过便利来对所有的输入都进行检测。那第二步是我们的核心逻辑，我们要去编写一个逻辑 来判断两个字符串他们是否互为字母意味词。那这里我们可以根据题目中描述的这个字母意味词的定义啊来进行一个分析。字母意味词是由重新排列原单词之后的所有字母得到一个新的单词， 那也就意味着说同一组字母意味词在经过重新排列了之后，他们是能够重新排列成一个相同的字母串啊，注意这个能够， 也就是说我们如果要有一种统一的处理方式的话，就是将所有的一组字母意味词按同样一种规则来进行处理， 之后他们的结果相同，那我们就可以通过这个相同的处理结果来判断他们是否是一组字母意味词了。那一般我们管这种方式叫做标准化， 就是通过一系列标准的这种的处理方式，然后将一批数据把它的结果统一成一个标准规格，这样的话便于后续的逻辑进行处理。他在工程里面是一种十分常见的手段。 那对于字符串来说就是一种统一的规则的话，我们首先可能想到的就是一个字典排序吗？就是从 a 到 z 的一个排列。 哎，炸药这种使用贴心呢，就有这种现成的工具类来帮我们去实现这种数组的排序啊，十分好用，一定要记住。呃， resort， 那到这一步我们就可以开始构建我们的代码了。 ok， 首先我们先构建一个基本的外层循环，然后来便利一下我们的输入参数，然后我们需要设置一个 map 来记录我们已经处理过的数据。 呃， map 的 key 是 stream， value 就是要接收的 list， stream 是用来聚合的数据。然后我们在内层循环里头就需要对每个 zoo tar 进行处理。 我们的目的是得到一个有序的 surprise， 所以我们先把我们的 string 取出来， 得到他的字符数组，然后调用我们的方法类去进行排序，再把排序好的字符数组，然后声称成一个字符串。 接下来我们就可以用这个植物串来进行判断了，如果卖不中存在这个植物串的话，那我们就直接将它 取出来，然后把它追加到已有的巨盒里头， 那如果里头不存在的话，那我们就需要去新建一个集合 list， 然后来去承接我们的结果。集合 添加完币了之后，再将它放到 map 里头， 那其实这一段 evols 的话就是见仁见智，你也可以用 get our default 去实现，但是我感觉可读性会差一点儿。然后我们将 map 的 values 结果创建一个新的 released 作为返回。 ok， 我们尝试运行一下。 好，这要是通过了哈， 那么之前我们针对第二步骤使用的是排序的方式来进行判断的。那么返回题目，我们重新思考一下，如果排序交换了之后 算作是意味词的话，也就是说明两个字符串只要他们的原料是相同的，组成他们的字符种类，每种字符的数量如果是相同，那么我们就可以判断他是意味词。 那我们构建一个叫做 word 的这个内部类，那他有一个这个 cons 的这个属性。我们再在这构造函数里头将字符输入进去，并且统计出来每一个字符串中每种字符的数量。 我们用冯云环啊，然后取一个二十六位的一个整形数组用来计数，那我们去循环字符串，将其中每一个字符对应 cons 里头的这个值进行累加，我们就得到了不同种类的字符在这个字符串里头所占据的总数。最终得到了一个可以描述这个字符 串儿的 cons 的一个数组，也就是 word 的这个类。与此同时呢，我们需要重写一下 word 类中的 hash code 方法和 ecose 方法，那以便于我们在 hash map 的时候，能够用这两个方法去将 word 类进行句类 okay 运行通过啊，甚至还快了一点。那原则上来说的话，第二种方法应该是累加的，他的方式的话是一个 on 的时间处理复杂度，而排序的方法是要显然高于他的， 但是由于其他的长数时间也有所差别啊，所以在题目中给定的这个数据，因为他的每个字符串的上限是一百，所以整体上的差距其实是不大的。 但是在面试的过程中的话，对题目的这个多维度的思考是加分的，所以这两种方法你都可以在进行对于题目的回顾或者分析的时候去提供给面试官。 ok， 我们第三题是最长连续序列，那给定一个未排序的整数数组，找出数字连续的最长序列 列，那题目中对这个连续的最长序列做了一个定义，不要求序列元素在原数组中连续，也就是说序列的意思是不用在数组中连续，他只要能够组合出来这样一组的数据就可以了。 最终是要找到这样一个序列的长度，并且底下有额外的条件，就是请你设计并实现一个时间复杂度为 on 的算法来解决此问题。 ok， 好了，给我们分析一下，题目中直接说了要使用 on 的算法，时间复杂度 o n， 也就意味着我们只能够对所有的数据进行一下长数次的处理，就是一遍或者是两遍是吧，他这一定是一个长数项的，就是这个便利的次数不能和数据量这个 n 有关的。那我们可以先从定义入手，连续序列具有什么样的特点？连续序列咱们抽象来看的话呢？他就是具有头、中部和尾三个部分，那头就意味着他之前是没有数字的， 那中部也意味着他前后是都有数字的，尾部则是他后面是没有数字的。 那显而易见，在这么一大堆的数据里头，咱们要找总共有多少个连续的序列的话，那其实我就可以去通过便利所有的投机点的方式 就找到了所有连续的序列了。因为我只要找到一个头接点，那我顺着头接点往后去一次查询的时候，就能够查询完所有这个连续序列的 中的所有数字，对吧？而当我们查询到一个头结点 n 之后，我们就可以通过判断是否存在一个 n 加一的数字来判断这个连续序列是否结束了。那如果存在这个 n 加一的节点的话，那我们就可以进一步的往后去判断， 然后再判断一下是否有 n 加二的节点，那如果有 n 加二的节点的话，那也就是说 n 加一的节点他是一个中部节点，因为他有后续的节点， 那如果没有 n 加二的节点的话，也就是说它是一个尾部节点，那如果我们发现当年判断的是一个中部节点的话，那我们就可以重复这个过程，重复这个过程一直到我们找到了一个尾节点为止。 当我们发现了一个尾节点的话，那也就是说这一个连续的序列已经结束了，我们可以通过之前存储的这个序列的长度来长 尝试更新我们的返回值。当我们将所有的序列头部都已经便利完毕了之后，我们就便利了所有的连续序列了，那这个时候我们就可以返回答案了。 ok， 那我们根据这个逻辑来尝试写一下。 首先我们先创建一个哈西集合，这样的话便于我们后续利用他来快速的定位是否存在目标的数字。复人环，把它触手画一下， 然后我们再用 count 来记录整个序列的一个长度，然后用这个 r a s 来记录返回值，就是我个人其实比较喜欢用 r a s， 因为就左手三个字母打的特别的顺， 然后我们对这个输入进行一个便利，这样的话就是让我们能够找到所有的连续序列的开头。那怎么办？ 判断开头呢？就是上面说的，判断一下是否存在他之前那个数字，那没有的话就说明这部分的是开头的一个序列， 接下来我们就可以顺着这个依次的进行判断，如果存在了后续的一个序列的话，那就是说明他有可能是一个中部的数字， 那如果要是一个中部数字的话，我们就可以对这个 count 进行个累加，并且将当前的这个数字移到下一位，就我们的这个 current， 然后当不满足了的话，也就是说我们已经发现了这个顺序序列的一个尾 步了，那这个时候我们就可以直接的去进行更新结果了， 判断一下当前的这个 count 值和历史的 r a s 的这个累积值到底是哪个大，然后更新 r a s， 最后我们就可以去返回，那我们测试一下 o k， 那至少是通过的啊，虽然有点慢， 那在返回我们的代码我们可以发现啊，虽然代码中是一个复式循环，其中牵踏了一个 well 的情况啊，乍看的话好像是一个欧文方啊，但是通过咱们书底这个逻辑就 可以发现，一个数字就输入的所有的这些数字里面的某一个数字，他至多只会被判断几次啊，先判断一次是否是前置数字， 然后是有可能会在 forum 环内通过 well 来判断是否存在后续数字，对，就只会判断两次，再加上处儿画的那个 sat 的爱德的话应该是三次，所以它整体来上的话是满足这个 o n 的需要的。 那哈西呢，作为一个日常工作中十分常用的数据结构，咱们要理解他的核心目的就是空间换时间的为打码提速。所以在后面的一些题中，咱们会遇到一些要求使用原地算法来进行处理的问题，也就是说他侧面上呢，限制了不允许使用 哈西的方法来进行提速。同时在进行题目阅读的时候，咱们不能忽视了数据规模的提示，他是可以对咱们的实现方案选型有指导性意见的。最后总结一下，两数之和，注意使用哈西来代替便利 字母意味词分组，咱们需要借助数据的重新标准化来制定哈西的规则，从而来聚合数据最长连续序列，需要通过分解目标结构的规则来实现分布的查找。就这样没事走了啊。
粉丝20获赞101
相关视频
14:56查看AI文稿AI文稿现在我们来看 litco 的编号七十题目，爬楼梯，它属于 litco 的热题，获得一百专题里面的题目之一。那么这个题目的问题是什么呢？这是假设说你正在爬楼梯，需要有 n 阶呢才能爬到楼顶， 每次只允许爬一个或者两个台阶，现在就要求呢有多少种不同的方法可以爬到楼顶？那么下面的四句就告诉我们，现在你输入 二表示说这个楼梯有两个街，那么有几种方法可以发到楼顶啊？那么就是两种，哪两种呢？第一种每次只走一个台阶，第二种， 一次走两个台阶。如果说这个楼梯有三三个台阶，那么就有三种方法可以爬到楼顶。第一种法还是每次只走一个楼梯，那么第二种方法是我 先走一个楼梯，再走两个楼梯，那么第三种方法是我先走两个楼梯，再走一个楼梯。那么现在问题就说， 现在假设说我们的阶梯有 m 个，问你有多少种不同的方法可以爬到楼顶？那么同学们，我们来仔细想一下这个题目，其实 当我们开始爬楼梯的时候，第一步有几种可能的结法只有两种，要么你就是走一个楼梯，要么你一次走两个楼梯。 那么同学们仔细想一想，我要爬完这嗯个楼梯的话，那么我走法的步数等于什么？其实又等于说我先走完一个楼梯 以后，剩下的楼梯也就剩下的 n 减一个楼梯，他有他的走法个数。我第一步先走两个楼梯，剩下的 n 减二个楼梯，又有什么呀？又有他的一个走楼梯的一个个数，所以说我 整个楼梯的一个走楼梯的个数其实怎么样？其实就是我走第一步走一个楼梯，加上我第一步走两个楼梯，这两个走法个数的一个相加， 那么用公式表示，其实就是什么 f n 减一，这表示说我第一步走第一个楼梯有多少种走法，加上谁加上 f n 减二，他就表示说我第 步如果走两个楼梯有几种走法？这其实可以看到 fm 等于 fm 加一加上 f， 哎，你讲啊，且其实这是什么？这就是一个地规公式。那么接下来我们就要看一下终止条件，当我们走到了快接近顶部的时候，当如果说只有一个楼梯的时候，还需要 地规吗？不需要地规了，只有什么？只有一种走法？也就所谓的 f 一等于一，但是这个地规中指条件够不够， 并不够。假设说现在有两个楼梯要走，那么也说 f 二等于， 按照我们这里的地规公式，它会变成什么？ f 二等于 f 一加上 f 零， 那么现在 f 一等于一我们是知道的， 那么现在要求什么？ 求 f 零。当然我们根据题目我们知道 f 二其实它是等于多少，它其实是等于二的， 那么也就意味着说我要求出 f 零的话，二一就 f 零，其实它就应该等于一，对不对？但是 f 零等于一， 从我们尝试来说，想起来这样有点滑稽，所以说这个时候我们可以怎么做？我们直接把 f 二等于二，也把它看作一种终止条件。 就说表说我走两个楼梯有怎么样？有两种走法，哪两种？要么我一次走完两个楼梯，要么我一步一步的走，比如说分成两步来走，所以说对于我们当前这个 fm 产生这么一个地规公式而已，他的终止条件其实就有两个，第一 f 一等于一，第二 f 二等于二，剩下的方式 大于二的楼梯的个数都要满足我们下面所看到的这一个地规公式。那么相对应的代码其实就很简单， 在我们代码里面三行代码就可以解决，如果 f n、 n 等于一的时候返回一，当 n 等于二的时候返回二，这表示属我们的一个地规的终止条件。那么 在我们的锐特里面，直接调用我们当前这一个地柜解法的方法本身就可以了，只不过传递出的参数是 n 减一和 n 减二，代码非常的简单，只有三行代码， 但是这种方法的实现，它的复杂度相对来讲是比较高的，如果说你把它放到我们立特寇德里面去执行的话， 有可能立德克的会告诉你执行时间超时，因为他的时间复杂度其实已经有多长了，其实已经有大卧 n 的平方会说他是比较慢的。 那么我们这种采用纯粹的这种地柜的实线同学们主要的问题是什么？其实是存在着一个重复计算的问题， 我们以六个楼梯，也就说 f 六来做一个简单的分析，那我们可以看到，在 f 六的求解过程中， 要求 f 六，我先求 f 五和 f 四，要求 f 五，我要求 f 三和 f 四，要求 f 四，我要先求 f 二和 f 三，要求 f 三，我要先求 f 二和 f 一， 那么求 f 四。刚刚我们已经讲过要 f 二和 f 三，对不对？你看在我整个 f 六的求解过程中， f 三与 f 四其实你被求解了多次， 这个其实怎么样？其实没有必要的，我已经求解过的东西，我为什么要重复求解呢？所以我们可以怎么样？我们就可以考虑使用一个什么，使用一个哈西 map 来保存。保存什么？保存在我求解的过程中已经求解过的 f 值， 比如说 fk， 这个是 fk， 求解过了，我就把它保存到我们的嗨系迈步里面去。当我下次求解的时候，再碰到这个 fk 的时候，我 先到什么？我先到这个哈西表里面去找一找这个 fk 我曾经有没有求解过，如果是我直接从哈西麦棚里面去找他的直播就可以了吗？这样做 不需要重复计算，就能够避免我们刚才所说到的重复计算的问题。那么这种方法他的执行时间复杂度呢？就为 o n， 那么对应的代码相对比我们前面来讲稍微要复杂一点。 那么除了最开始的两个终止条件以外，我们多引入了一个含蓄脉补，专门用来存放我们在求解过程中的中间值。 那么每当碰到一个 m 的时候，首先到哪里？到这个韩信卖部里面去获取，如果说能够获取到， 直接把我迈普的值作为我们 n 当前的一个求解的结果返回出去。如果说这个值在我们的哈西麦普里面没有存在过，那么怎么样？我调用地规的方式来求解当前这个 n 是多少？然后把求解的结果值同样也要放到我们的哈西麦普里面去，这就是这就是我们带来哈西麦普的这种方式的这么一个 地规方式解决方案，那么这种解决方案他的时间复杂度，刚刚说他是一个大窝的 m， 也说他这个线性的实践复杂度，那么 具体执行下，我们提交一下河水呢？和我们立特库的上面已有的体检做一个相对的比对，可以看到 我们这种求解执行号是只要零毫秒击败了百分之一百的用户。当然在我们 真实的刷题过程中，没有必要去追求，我每一个体检都要求达到百，超越百分之百的用户，基本上你能够达到百分之八十， 你的结法已经是比较优秀了，当然我跟他说越高越好，但是如果说你时间紧张的话，没有必要去硬是要去追求百分之九十乃至百分之一百，那么也说在我们刷题的过程中，首先关注应该是执行用时这个内存消耗，一般来讲我们不要太去关注他。 好，现在是说我们用地规的方式来求解爬楼梯，那么有没有用非地规的方式来求解呢？那么在这 一个解法中，我们可以用到地规的解法是什么呀？他是一个典型的置顶向下，由最开始顶层的这个数字一层一层的分解， 一直分解到哪里，一直分解到中指条件。那么在我们爬楼梯里面，你就说分解到 f 二和 f 一，然后再一层一层的怎么样把结果往上进行一个累累加， 那么如果说我要地规改成循环怎么去改，那么我循环的结法 我就可以怎么样可以直接由底向上，因为我最底层的 f 二和 f 一我是 知道的，我就从 f 二和 f 一开始直接垒加上来即可，而且 从我们往上进行累压的过程中，我们可以看到 f 二加 f 一可以得到 f 三的值， 而我 f 四的值要求解，要先知道 f 三与 f 二，那么也就是说在我 上一个循环中我求出的 f 三这个值，在我求解 f 四的过程中，我是完全可以利用上的。 同理我要求解 f 五也要用到我上一个循环中我要用到的 f 四，那么也就是说在我使用循环 来求解这个爬楼梯的过程中，我可能需要单独需要两个额外的变量来保存什么？来保存我每一层求解中他所需要的两个 只问题的这么一个结果，所以对应的代码 应该是怎么样？对应的代码就应该是这个样子， 终此条件依然要保留。 比如说 n 等于一的时候直接返回一， n 等于二的时候直接返回，是吧？直接返回二， 那么引入了三个局部变量，普瑞和普瑞和两 哥。普瑞这个变量专门用来存储我们所需要的一个中间过程，所以绕着作为最后的一个结果 返回出去，那么我们的循环就应该从哪里从三开始，因为一和二我们是已经知道了结果，不用去额外计算了的。 然后在这个循环里面，我们的结果就是嘛，就是前两个结果的一个什么，一个相加。那么很明显 最刚开始循环的时候，我的普瑞和普瑞，普瑞这两个变量词分别是二和一，当我们算出了三的结果以后，我们应该怎么样？ 就应该进行一个相关的中间变量的替换，让我们的普瑞和普瑞的字 等于普瑞，那么没错，这个时候他的形态他的值就应该等于二，而普瑞的值就应该用我们刚刚所算出的瑞绕特进行替换，那么也就说普瑞的值就变成了三这样一层一层的由底向上， 最后循环上去就能够得到最终 n 情况，下面我爬楼梯的次数或者 这个解决的方法个数到底有几个好？那么由地规改成循环以后，我们来看看他的执行效率到底怎么样？来提交一下， 那么可以看到我们采用循环加地规的方式执行的用时依然可以提交，怎么样可以击败百分之 百的用户，所以说采用循环的解法，他的执行效率依然是不错的，而且这种方法的执行的时间复杂度很明显，他知道他也是一个大窝 m， 也是一个线性的实践复杂度，那么从我们地规的实线和非地规的实线来看，很明显我们用循环来取代地规的时候，在代码的复杂度上也要复杂一些， 同时呢也比较难以理解一些啊。这也是往往说为什么说在实际工作过程中，或在面试过程中，我们更说可能更加倾向于地柜来解决问题。
09:04查看AI文稿AI文稿我们来看一下立扣四十八，找到所有数组中消失的数字，那么这个题目呢？属于立扣热体获得一百专题里面的题目之一，那么这个题目描述什么呢？所以说现在有一个包含 n 个整数的数组，那么死其中 这个数中的俗话有的元素它的值啊在区间一到 m 之内，现在都需要找出说所有在一到 m 的范围之内，但是在我们的数组中没有出现过的数字，并且以数组的形式去反馈结果， 那么下面的视力也表明的很清楚了，我们的纳木斯这个数组中间包含的元素有四三二七、八二、三一，可以看见这个数组他的元素个数为几个？为八个啊，所有的数大小范围也 到一在八之间，但是在这一些元素的值里面，二和三是重复出现了，那么这个那么死里面就缺失了一到八中间的五和六。现在题目就要求我们找出谁找出这个五和六， 那么这个题目怎么做？我们可以怎么样？可以考虑说我们引入一个哈西表， 用一个哈西表去记录什么呀？去记录在我的纳木子中出现了哪些数字，然后 把数字数字全部记录以后，我们通过检组这个哈西迈普就知道说在一到八之间哪几个数字在我们的数中没有出现过，但是题目中有 额外的进阶要求，表示说不能够使用的额外空间，且时间复杂度为 n 的情况下来解决这个问题，用哈西麦普来解决时间复杂度这个是满足的， 但是不使用额外空间这一点是不满足的，因为你单独拿出一个哈西迈步来存放什么？来存放这个纳木斯中中元素的 值，所以说在这种情况下面使用哈西迈步，空间复杂度又会变成大窝 m， 不符合我们题目境界的要求，所以呢，这种方式我们不考虑。那么怎么做呢？不使用哈西麦普能不能做到？当然是可以的，因为现在我们的题目要求是什么？要求是找到所有在数组中消失的数字，那就意味着 必须要有一个地方去记录什么，这些数字哪些在数组中出现过，哪些没有出现过，怎么办？又不能用额外的空间，这个时候我们就要考虑使用谁使用我们数组本身了。 那么具体做法是什么呢？因为我们知道这个速度的长度是多少？速度的长度本身它是为 n 的， 而我们数组中每一个元素他的数字的范围在一到 m 之间， 所以我们可以利用什么？我们可以利用这个范围之外的数字来记录什么？ 来记录数字是否出现过。比如说给我数字中的每一个元素都加某一个值， 或者说把我们竖中的元素他的词变成一个复数都是可以的。那么比如说我们先用复数来演示这个过程，现在我们已知 速度是一零是四三二七八二三一这一些数字好，于是我们把下标移到第零号元素上，现在第零个元素的数字是多少？是四， 那么我们怎么办？我们把四减一等于三，那么也就是说下标为三的元素，把它改为什么？把它的值改为一个负七， 那么第一个元数多少？第一个元数是三好，三减一等于 二，所以我们把第二个元素把他的对应的值改成多少，改成负二。当然在这个过程之中，我们对数读的是什么，他是一个便利过程，所对应的这个 指示器肯定要跟着做一个相关的移动，那么通过这么一番把数组便利便移过一次以后，那么这个时候会变成什么样子呢？你就会发现在这个数组之中， 除了四和五还是正数以外，其他的数都变成什么都会变 变成一个负数，这个时候我们就可以怎么样，我们就可以知道四和五所对应的这两个数，他在我们的速度中没有出现过，所以最终缺失值就是四加一 等于五和五加一等于六也，那么也就说五和六在我们当前的原始数组中他是没有出现过的，那么这是说把数字变成一个负数 加一个数呢？加一个数的思路也是一模一样的，但是稍微注意一下，我们加的这个数要怎么样， 要有所取舍，因为你加完以后，因为说别说你是加上某一 一个数以后，这个数是怎么样不能在我的原始数组中出现过， 那么这个加入我们可以设置为多少？我们可以设置为 n， 那么这个 n， 因为我们知道数组纳木斯他的范围哪里，数组纳木斯他的数字范围是在一到 n 之间的， 所以加上 m 以后，可以保证说在我那么死这个数组里面，加完以后最小的数也是 m， 加一 不会怎么样，不会和我数组中本来的原数数据进行一个相关的冲突，那么就可以避免我们刚开前面所说的这个问题，那么在实际代码实验大家还要注意一点，注意点什么呢？因为说我们说 当中这个数字他有可能重复过，对不对？而且在我们去不管你是家还是说把变成复数情况，比如说你看我们前面，我们对对，我们对这个事做错了的时候会影响几，会，影响多少？会影响 三号下面八八变成一个夫妻。那么所以说我们辨认到某一个数的时候，可能出现这个数字被什么呀？被改过的情况， 那么这个词呢，就还需要在实际代码实现的时候就需要怎么样，还需要进行一个判断和还原这么一个情况。那么大家采用这种方式来实现以后，我们很容易分辨出，因为在我的整个执行过程中，我怎么样，我往往对数字 数组只循环了两遍，第一遍检查所有的原数数中的数字，第二遍找出其中哪一些没有被修改过，所以说它的时间循环度，时间复杂度是大 o r m， 也就是大 o m， 那么空间复杂度呢？自然就是 oe 了，因为我们没有使用任何额外的空间。那么对待代码应该怎么写？那其实很简单，首先第一步 就是对这个数组进行一个什么，进行一个相关的循环，不管说你是变成复数也好，还是说对他进行累加也好，都没有任何问题。把通过在一轮循环里面，按照我们刚才所说的那种处理 思路，把所有的数字中的所有的数字做了一次变化以后，在第二遍循环里面找出所有 为负数，为负数啊，或者说是所有大于 m 的数把它找出来，那么这个时候我们说这种数字中缺失的数字自然而然 就能获得了。那么按照这种思路解决以后效率如何呢？我们没用哈西麦 效率运行下可以看到我们执行的总时间或者花了三个毫秒击败了百分之百的用户，说明我们当前这个实践他的效率还是比较 ok 的。
![给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。
请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。](https://p3-pc-sign.douyinpic.com/tos-cn-v-22574f/ogDQgCIb3C9QpR0NifPlqF8vcL9nqjgAC9HaeB~tplv-dy-resize-origshort-autoq-75:330.jpeg?lk3s=138a59ce&x-expires=2099350800&x-signature=2sGs0%2FjK3cBue9LqY50hmzk1hI0%3D&from=327834062&s=PackSourceEnum_AWEME_DETAIL&se=false&sc=cover&biz_tag=pcweb_cover&l=20260714090357A32AD8B358AC385A9939)
