字节跳动leetcode算法题

A. leetcode算法—[面试题 05.02]二进制数转字符串（中等）

问题难点一：了解小数转换为二进制的定义。

思路： 循环操作，每次num*2，判断是否大于等于1？true：则填充1，false则填充0，直至num为0时终止循环！

遇到的难题：

按照题目分析，0.1是无法转换为二进制的。因为 0.1->0.2->0.4->0.8->0.6->0.2->0.4....会一直循环下去。

那么不能转换为二进制的小数有什么规律呢？思维卡在这个误区。

结题思路： 将循环的num变量均缓存起来，然后判断num变量是否出现重复的情况。若出现重复则直接返回ERROR。

但是实际运行起来， 出现了double精度的问题 ，导致num并不是0.6而是无限接近0.6，故使用缓存的思路是行不通的。

题目中明确表示，若无法使用32位二进制表示，则打印error。

那么结束循环的条件：num为0或者循环的次数为32次。

B. 字节跳动笔试通过率

1、一道算法题，字节跳动非常看重算法，算法的难度大概在LeetCode中等难度且通过率在30%以上的，比重40分，如果你想靠背答案来过关，那么最好是打消这个念头，因为做出来只是前面，后面会有更深入的问题，比如：时间复杂度、空间复杂度和优化点等；

3、iOS基础，基本上就是一些面经和源码级别问题什么的，比重40分，如果真的问到了你不会的，那么回答的模板是：这个问题呢我没有深入的去了解，我只能说一下我的观点，然后把你掌握的相关的知识说一遍，然后推出一个可能的结果。

C. 算法笔记之前缀树——字典序的第K小数字

前缀树（字典树）的一种应用场景，和传统的前缀树使用不太一样，但是使用了其中的思想。

LeetCode 440. 字典序的第K小数字

定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

题目描述比较简单，据说这是字节跳动面试喜欢出的一道题。

首先简单解释下，字典序就是1、10、11、12这样按照类似字典一样的字符顺序排序数字。

既然要用前缀树的思想，那么我们先把前缀树画出来。

我们可以看到相同前缀的数字可以放到一个子树里，子树的每个层级依次有1、10、100...个节点。

我们可以先判断数字k属于哪个子树，然后在当前子树往下一层级移动。然后重复找子树和往下层移动的过程，直到找到节点（也就是数字）。

D. leetcode算法

*最近在做一些 leetcode 的算法题，我会将自己做过的算法题记录下来以供大家参考，如果查找不方便请看 油猴插件实现网站左侧目录生成。

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例：

解答：

     

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

提示：

解答：

     

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例：

说明:

解答：

     

给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例：

解答：

     

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例：

解答：

     

给定两个数组，编写一个函数来计算它们的交集。

示例：

说明：

进阶:

解答：

     

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例：

解答：

     

给定一个数组 nums ，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

说明:

     

给定一个整数数组 nums 和一个目标值 target ，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例：

解答：

     

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

说明:

解答：

     

给定一个 *n *× *n* 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。

说明：
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。 请不要 使用另一个矩阵来旋转图像。

示例：

解答：

     

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须 原地修改输入数组 、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例：

解答：

     

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例：

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

解答：

     

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

解答：

     

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
长度一样，包含的字母都一样，每个字符出现的频率也一样，只是顺序不同而已，这就属于异位词，

示例：

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解答：

     

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明 ：本题中，我们将空字符串定义为有效的回文串。

示例：

解答：

     

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

注意 ：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示 ：

示例：

解答：

     

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始) 。如果不存在，则返回 -1 。

示例：

说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符

解答：

     

“外观数列”是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1 被读作 "one 1" ("一个一") , 即 11 。
11 被读作 "two 1s" ("两个一") , 即 21 。
21 被读作 "one 2", "one 1" ("一个二" , "一个一") , 即 1211 。
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意 ：整数序列中的每一项将表示为一个字符串。

示例：

解答：

     

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 "" 。

示例：

说明:
所有输入只包含小写字母 a-z 。

解答：

     

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例：

说明：

解答：

     

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

说明：
给定的 n 保证是有效的。

进阶：
你能尝试使用一趟扫描实现吗？

解答：

     

反转一个单链表。

示例：

解答：

     

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

解答：

     

请判断一个链表是否为回文链表。

示例：

解答：

     

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1 ，则在该链表中没有环。

示例：

解答：

     

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明 : 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7] ，

返回它的最大深度 3 。

解答：

     

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

示例：

解答：

     

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

解答：

     

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树： [3,9,20,null,null,15,7] ,

返回其层次遍历结果：

解答：

     

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例：
给定有序数组: [-10,-3,0,5,9] ,
一个可能的答案是: [0,-3,9,-10,null,5] ，它可以表示下面这个高度平衡二叉搜索树：

解答：

     

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明:

示例:

解答：

     

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n] ，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例：

解答：

     

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意 ：给定 n 是一个正整数。

示例：

解答：

     

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意 ：你不能在买入股票前卖出股票。

示例：

解答：

     

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

解答：

     

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例：

解答：

     

打乱一个没有重复元素的数组。

示例：

解答：

     

设计一个支持 push ， pop ， top 操作，并能在常数时间内检索到最小元素的栈。

示例：

解答：

     

写一个程序，输出从 1 到 n 数字的字符串表示。

示例：

解答：

     

统计所有小于非负整数 n 的质数的数量。

示例：

解答：

     

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

示例：

解答：

     

罗马数字包含以下七种字符: I ， V ， X ， L ， C ， D 和 M 。

例如，罗马数字 2 写做 II ，即为两个并列的 1 。 12 写做 XII ，即为 X + II 。 27 写做 XXVII , 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII ，而是 IV 。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX 。这个特殊的规则只适用于以下六种情况：

示例：

解答：

     

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量 ）。

示例：

提示：

E. leetcode算法-给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和

初次看到这个题目，没有考虑到大数相加问题，所以直接的思路是：

具体实现如下：

但是执行leetcode的测试用例，没有通过，挂在了 addStrings('9333852702227987', '85731737104263') 这两个数据的计算上。如下图所示：

看到这里，让我想到了这应该是大数相加的问题，那我们一起再学习一下大数相加的问题吧，然后我们再解题：

因为 JavaScript 的 Number 类型是遵循 IEEE 754 规范表示的，这就意味着 JavaScript 能精确表示的数字是有限的， JavaScript 可以精确到个位的最大整数是9007199254740992，也就是2的53次方，超过这个范围就会精度丢失，造成 JavaScript 无法判断大小，从而会出现下面的现象

在网上找了一张图，表示的比较形象，也不知道来源是哪里的，很多人的博客里都有这张图，我们也借来参考下：

解决方案思路其实比较简单，就是将字符串转换为数组，末尾对齐，数组的两两元素相加得到total，如果total大于10的话，就往下一位进1，本次计算这一位对10求余数(temp % 10) + res做拼接。最后得到的结果就是精确的。通过这个思路，可以实现下leetcode这道题，本质也是大数相加问题：

执行效率如下图所示：

F. 字节交叉面试会考算法吗

会的。
1.字节跳动并不会特别关心候选人使用什么编程语言，逻辑很简单，你Java特别厉害，那转Go语言肯定不难。当然，如果你觉得难，那大概率也通不过后面的面试。
2.在整个的面试流程中，至少会有3轮技术面，并且每一轮面试都会考算法。不管你是工程师，还是架构师。
3.为什么要考这么多算法？其实核心是看候选人是不是足够聪明。和Netflix一样，字节跳动招聘工程师的必要条件就是聪明。
4.怎么考算法呢？一般会分两步，第一步是直接让你说思路，第二步是让你直接上手写代码。字节跳动的算法题一般对应的是LeetCode中级模式，要通过面试，你肯定得花时间好好准备。
5.写算法代码的时候，你可以用白板，也可以用电脑，都行。常见的模式是给你20分钟时间，让你写出来某道题的解法。当然，肯定是越快做出来越好，这能说明你的熟练程度。

G. LeetCode题解：跳跃游戏II

给你一个非负整数数组nums，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。

输入： nums = [2,3,1,1,4]
输出： 2
解释： 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

这道题是典型的贪心算法，通过局部最优解得到全局最优解。以下两种方法都是使用贪心算法实现，只是贪心的策略不同。

我们的目标是到达数组的最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，该位置通过跳跃能够到达最后一个位置。
如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？直观上来看，我们可以使用贪心的选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此我们可以从左到右遍历数组，选择第一个满足要求的位置。
找到最后一步跳跃前所在的位置之后，以此类推，直到找到数组的开始的位置。

复杂度分析

方法一虽然直观，但是时间复杂度比较高，有没有办法降低时间复杂度呢？
如果我们贪心地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。
例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。
从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。

复杂度分析

H. 耗时7天我终于把LeetCode刷通关：数组十七连，真是不简单

大家好，我是老三，一个刷题困难户，接下来我们开始数组类型算法的刷题之旅！

数组

数组基本上是我们最熟悉的数据结构了，刚会写“Hello World”不久，接着就是“杨辉三角”之类的练习。

数组结构

上图是一个字符数组的例子。

因为内存空间连续，所以可以直接通过下标获取对应的元素。

但是删除就麻烦一点，相当于填坑，一个元素被移走，留下的坑，需要其它元素来填上。

删除元素

在Java中，多维数组的存储本质上也是一个行优先的一维数组。

我们都知道，在Java中的 “=” 用在基本数据类型上，是值传递，用在引用数据类型上，是引用传递。

这一块展开可以写一篇文章，我们只简单看个例子：

大家可以看到，newArray改变了，array也跟着变了。

为什么呢？

在Java中，数组是引用数组类型。array、newArray都是存储在栈中的引用，它们指向堆中真正存储的数组对象。

所以改变了newArray，实际是改变了newArray指向的数组。

数组引用传递

这一点是我们刷题需要注意的，复制数组需要在循环中一个个复制。

题目：704. 二分查找 (https://leetcode-cn.com/problems/binary-search/)

难度：简单

描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

题目示例

思路：

二分查找可以说我们都很熟了。

因为数组是有序的，所以定义三个指针，low、high、mid，每次与中间指针指向的元素nums[mid]比较，

二分查找

但是这个代码还有一处问题，在哪呢？

int mid = (left + right) / 2;

这个地方可能会因为left和right数值太大导致内存溢出，所以应该写为 int mid = left + ((right - left) >> 1);

修改之后代码如下：

时间复杂度：O(logn)

题目：35. 搜索插入位置 (https://leetcode-cn.com/problems/search-insert-position/)

难度：简单

描述：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

题目示例

思路：

二分查找比较简单，但写对还要费点功夫，再做一道基本一样的题巩固一下。

这道题基本一样，插入的位置可能有四种情况：

二叉树插入位置

代码如下：

时间复杂度：O(logn)

题目：34. 在排序数组中查找元素的第一个和最后一个位置 (https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

难度：中等

描述：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

题目示例

思路：

看到时间复杂度 O(log n) ，数组有序，我们知道，二分查找该上场了。

但是这道题有点不一样，它需要寻找边界。

那我们怎么办呢？

这就引入了寻找边界的二分查找。

这道题的思路是什么呢？

我们分别用二分查找来寻找左边界和右边界。

一般的二分查找：

注意，我们这里的返回条件是 nums[mid] == target ，但是寻找边界的时候就不能这样了，因为我们不能确定mid是不是我们的边界。

以寻找左边界为例，条件是 target <= nums[mid] 的时候，我们接着往左移动。

寻找右边界也类似。

代码如下：

时间复杂度：O(logn)

题目：27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)

难度：简单

描述：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

思路

“暴力解法”

暴力解法没什么好说的，和上道题类似，找到要删除的元素，把它后面的元素全部向前移动一位。

暴力解法

这里有两点需要注意：

代码如下：

时间复杂度：O(n²)。

“双指针法”

双指针法，是数组和链表题中非常常用的一种方法。

这道题用双指针法怎么解决呢？

定义两个指针，一个前，一个后。没有找到目标的时候front和after一起移动，找到目标的时候，after停下来，front接着移动，把front指向的值赋给after指向的值。

这样一来，双指针就通过一个循环完成了双循环完成的事情。

双指针法

代码如下：

时间复杂度：O(n)。

题目：27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)

难度：简单

描述：

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

题目示例

思路

趁着上一道题劲儿还没缓过来，赶紧做一道基本一样的巩固一下。

直接上代码：

时间复杂度：O(n)。

题目：283. 移动零 (https://leetcode-cn.com/problems/move-zeroes/)

难度：简单

描述：

给定一个数组 nums ，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

“示例:”

“说明” :

思路

继续沿着上一道题的思路。

移动零

代码如下：

时间复杂度：O(n)。

题目：977. 有序数组的平方 (https://leetcode-cn.com/problems/squares-of-a-sorted-array/)

难度：简单

描述：

给你一个按 “非递减顺序” 排序的整数数组 nums ，返回 “每个数字的平方” 组成的新数组，要求也按 “非递减顺序” 排序。

题目示例

思路

“暴力排序法”

这道题一看，最直观的做法是什么呢？

先求数字平方的数组，然后再把新数组排序。

代码也好写：

时间复杂度：遍历时间复杂度O(n)，快排时间复杂度O(nlogn)，所以时间复杂度O(n+nlogn)。

思路

“双指针法”

我们连写几道双指针了，这道题能不能用双指针实现呢？

我们分析一下，这个数组在取平方之前，是有序的，那么它绝对值最大的数一定是在两端的。

所以我们可以定义两个指针，一个指向最左端，一个指向最右端，比较两者平方的大小，大的平方放入结果数组，并移动指针。

有序数组的平方

代码如下：

时间复杂度：O(n)。

题目：1. 两数之和 (https://leetcode-cn.com/problems/two-sum/)

难度：简单

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

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

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

题目示例

思路：

“暴力解法”

上来我们先来个最简单的暴力解法，大家应该都知道冒泡排序吧，类似的两层循环。

两层循环

代码写起来也很简单：

时间复杂度：看到这个双循环，就知道时间复杂度O(n²)。

“哈希辅助法”

时间复杂度O(n²)多少有点过了，这道题的重点是两个元素相加之和的判断。

我们可以用一个Hash集合把元素存起来，这样一来遍历一遍就够了，例如目标和9，当前元素2，只需要判断集合里是否有元素7就行了。

时间复杂度：从Hash查询和取值时间复杂度都是O(1)，所以整体时间复杂度是O(1)。

题目：15. 三数之和 (https://leetcode-cn.com/problems/3sum/)

难度：简单

描述：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为0且不重复的三元组。

注意：答案中不可以包含重复的三元组。

题目示例

思路：

“哈希法”

做完两数之和以后，我们首先想到的就是哈希法。

两层循环，取到a，b，再通过 0-(a+b) 来确定c。

但是这里还有一个问题， 答案中不可以包含重复的三元组。

所以，我们还要想办法去掉Hash里的重复元素。

可以加入一个约束，第三个数的索引大于第二个数才存入。

时间复杂度：双循环，O(n²)。

虽然这么也写出来了，但是，说实话，很难写出没有问题的代码。

我们写了这么多双指针，那么有没有可能用双指针的方式呢？

“双指针法”

首先对数组进行排序，然后遍历数组。

然后再在当前节点后面取左右指针，判断左右指针的值是否等于0-nums[i]，然后分别左右移动。

怎么去重呢？

满足条件时，看左指针的值是否和前一个位置相等，右指针的值是否和和它后一个位置的值相等。

双指针法

代码如下：

时间复杂度：O(n²)

题目：18. 四数之和 (https://leetcode-cn.com/problems/4sum/)

难度：简单

描述：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

题目示例

思路：

我们延续三数之和的思路，在三数之和外面再套一层循环。

时间复杂度：O(n³)

题目：209. 长度最小的子数组(https://leetcode-cn.com/problems/minimum-size-subarray-sum/)

难度：中等

描述：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

题目示例

思路

这道题是一道经典的滑动窗口问题[4]。

image-20210801164436322

代码如下：

时间复杂度：O(n)，虽然循环里套循环了，但是starrt和end各自被移动了n次，所以时间复杂度是O(n)。

题目：219. 存在重复元素 II (https://leetcode-cn.com/problems/contains-plicate-ii/)

难度：简单

描述：

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

题目示例

思路：

上面我们做了一道滑动窗口的题，我们接着再做一道也可以用滑动窗口解决的问题。

这道题的滑动窗口略有区别，上一道题的窗口是活动的，这个是 固定的滑动窗口 ,维护一个长度为k的固定窗口，如果窗口内含有目标值，返回。如果窗口进入新的元素，就需要把头部的元素移除掉，保持窗口的长度。

固定窗口

代码如下：

时间复杂度：O(n)。

题目：1052. 爱生气的书店老板(https://leetcode-cn.com/problems/grumpy-bookstore-owner/)

难度：中等

描述：

今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。

在某些时候，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。

请你返回这一天营业下来，最多有多少客户能够感到满意。

“示例：”

思路：

这道题是一道固定窗口的问题。

整体思路就是把不生气的部分作为固定窗口，固定窗口把customers分成了三部分，最后求三部分的最大和。

固定窗口

时间复杂度：O(n)。

空间复杂度：O(1)。

题目：面试题3. 数组中重复的数字 (https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)

难度：复杂

描述：

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

“示例 1：”

思路：

“哈希法”

这种找重复的数字问题，我们脑子里第一下就想起来，用Hash存储元素，然后进行比对。

代码实现也很简单：

时间复杂度：O(n)。

空间复杂度：O(n)

但今天的主角不是它，而是

“原地置换法”

我们注意到一个条件 所有数字都在 0 n-1 的范围内 ,那就在这方面进行操作，我们可以把元素放到它的值对应的下标的位置。

例如 num[2]=1，那我们就把它放到下标1的位置。

接着遍历，元素发现它应该待的坑已经被它的双胞胎兄弟给占了，它就知道，它是多余的那个。

原地置换

代码如下：

时间复杂度：O(n)。

空间复杂度：O(1)

题目：41. 缺失的第一个正数 (https://leetcode-cn.com/problems/first-missing-positive/)

难度：复杂

描述：

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

题目示例

思路

“辅助数组”

这道题有一个非常巧妙地的办法！[1]

可以引入一个辅助数组，从1开始，在对应的位置存入原数组对应的元素。如原数组num[0]=1，那么这个元素就应该存入辅助数组 helper[1]。

然后遍历辅助数组，发现的第一个坑就是缺失的第一个正数。

辅助数组

代码如下：

时间复杂度：O(n)。

空间复杂度：O(n)。

“原地置换法”

我们上面用了原地置换法解决了一个问题，降低了空间复杂度，我们这道题是不是也可以呢？

原地置换没法修改数组长度，我们肯定不能nums[i] 存 i 了，我们左移一下，num[i-1]存i。

原地置换

代码实现如下：

时间复杂度：O(n)。

空间复杂度：O(1)。

题目：54. 螺旋矩阵 (https://leetcode-cn.com/problems/spiral-matrix/)

难度：中等

描述：

给你一个 m 行 n 列的矩阵 matrix ，请按照 “顺时针螺旋顺序” ，返回矩阵中的所有元素。

示例 1：

示例2

思路

这道题，思路比较容易想，就是上右下左四个方向顺时针遍历数组。

顺时针遍历数组

但是这道题的细节是魔鬼。

有两种，一种是一圈遍历完成，上下左右的位置移动，遍历是左闭右开[的条件。

我们采用的是第二种，每遍历完一条边，就移动对应的位置，遍历就是左闭右闭的条件。

还有一点细节就是值得注意的是，遍历过程中可能会出现出现 top > bottom || left > right ，其中一对边界彼此交错了。

这意味着此时所有项都遍历完了，如果没有及时 break ，就会重复遍历。

代码如下：

时间复杂度：O(mn)，其中 m 和 n 分别是输入矩阵的行数和列数。

题目：59. 螺旋矩阵 II (https://leetcode-cn.com/problems/spiral-matrix-ii/)

难度：中等

描述：

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例

思路

和上面一道题基本一模一样，我们往里面套就行了。

代码如下：

时间复杂度：O(n²)

剑指 Offer 29. 顺时针打印矩阵 也是一道类似的题目。

写了个顺口溜总结一下：

I. 这道题能解释一下吗

可以，
假设除以4的商为a余数为j，初一3的商为b余数为k
那么可得
n=4a+j
n=3b+k
可以换算成
3n=12a+3j
4n=12b+4k
两式相减得
n=12b+4k-12a-3j
n=12(b-a)+(4k-3j)
即能除以12余4k-3j，所以除以6必定也余4k-3j，如果算出来是负数或者大于6，取正值或者再除以6即可

J. LeetCode算法题-29. 两数相除（Swift）

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

示例 2:

说明:

之前 的方法都超时了，这个方法也只击败了70%的用户。但是我实在想不起来，不使用乘法、除法和 mod 运算符还能怎么优化。先这样吧。