用于编码面试的数组备忘单
简介
数组在连续的内存位置保存相同类型的值。在数组中，我们通常关心两件事——元素的位置/索引和元素本身。不同的编程语言以不同的方式实现数组，并且会影响对数组进行操作的时间复杂度。在 Python、JavaScript、Ruby、PHP 等语言中，数组(或 Python 中的 list)的大小是动态的，创建数组时不需要预先定义大小。因此，人们通常更容易在面试中使用这些语言。
数组是面试中最常见的数据结构。询问其他主题的问题也可能涉及数组/序列。掌握阵法对于面试来说至关重要！
优势
- 用一个变量名存储多个相同类型的元素
- 只要有索引，访问元素就很快，而不是像链表那样从头开始遍历。
缺点
- 向数组中间添加元素或从数组中间移除元素很慢，因为需要移动剩余的元素来容纳新的/缺失的元素。一个例外是，如果要插入/移除的位置在数组的末尾。
- 对于某些固定数组大小的语言，它在初始化后不能改变其大小。如果插入操作导致元素总数超过大小，则必须分配一个新的数组，并复制现有的元素。创建一个新数组并传递元素的行为需要 O(n)时间。
学习资源
- 读物
- 数据结构中的数组:什么是数组运算，Guru99
- 录像
- 阵列，加州大学圣地亚哥分校
常用术语
在处理涉及数组的问题时，您会看到一些常见术语:
- 子数组-数组中连续值的范围。
- 例如:给定一个数组
[2, 3, 6, 1, 5, 4]，[3, 6, 1]是一个子数组，而[3, 1, 5]不是子数组。
- 例如:给定一个数组
- 子序列——通过删除一些元素或不删除任何元素，而不改变剩余元素的顺序，可以从给定序列中导出的序列。
- 例如:给定一个数组
[2, 3, 6, 1, 5, 4]，[3, 1, 5]是一个子序列，但是[3, 5, 1]不是一个子序列。
- 例如:给定一个数组
时间复杂度
| 操作 | 大 O | 注意 |
|---|---|---|
| 接近 | O(1) | |
| 搜索 | O(n) | |
| 搜索(排序数组) | O(log(n)) | |
| 插入 | O(n) | 插入需要将所有后续元素向右移动一位，这需要 O(n) |
| 插入(在末尾) | O(1) | 不需要移动其他元素的特殊插入情况 |
| 去除 | O(n) | 移除需要将所有后续元素左移一位，这需要 O(n) |
| 移除(在最后) | O(1) | 不需要移动其他元素的特殊移除情况 |
面试时要注意的事情
- 澄清数组中是否有重复值。重复值的存在会影响答案吗？它使问题更简单还是更难？
- 当使用索引迭代数组元素时，注意不要越界。
- 请注意在代码中分割或连接数组。通常，分割和连接数组需要 O(n)时间。在可能的情况下，使用开始和结束索引来划分子数组/范围。
拐角情况
- 空序列
- 具有 1 或 2 个元素的序列
- 具有重复元素的序列
- 序列中的重复值
技巧
注意，因为数组和字符串都是序列(字符串是字符数组)，所以这里的大多数技术都适用于字符串问题。
滑动窗口
掌握适用于许多子数组/子串问题的滑动窗口技术。在滑动窗口中，通常向同一方向移动的两个指针永远不会互相超越。这保证了每个值最多只被访问两次，时间复杂度仍然是 O(n)。例子:无重复字符的最长子串，最小尺寸子阵列总和，最小窗口子串
两个指针
两个指针是滑动窗口的一个更一般的版本，指针可以互相交叉，可以在不同的数组上。例子:排序颜色，回文子串
当您有两个数组要处理时，通常每个数组有一个索引(指针)来遍历/比较这两个数组，相关时递增其中一个指针。例如，我们使用这种方法来合并两个排序后的数组。例子:合并排序后的数组
从右侧穿越
有时你可以从右边开始遍历数组，而不是传统的从左边开始。例子:每日气温，可见排队人数
排序数组
数组是排序的还是部分排序的？如果是的话，某种形式的二分搜索法应该是可能的。这通常也意味着面试官在寻找比 O(n)更快的解决方案。
你能给数组排序吗？有时，首先对数组进行排序可能会大大简化问题。显然，如果需要保持数组元素的顺序，这是行不通的。例子:合并间隔，非重叠间隔
预计算
对于涉及子阵列的求和或乘法的问题，使用散列或前缀/后缀和/积的预计算可能是有用的。例子:除自身数组的乘积，最小子数组和， LeetCode 问题标注“前缀-和”
作为散列关键字的索引
如果给你一个序列，而面试官要求 O(1)空间，那么可以用这个数组本身作为哈希表。例如，如果数组只有从 1 到 N 的值，其中 N 是数组的长度，则对该索引处的值求反(减一)以指示该数字的存在。例子:第一次不见正，每日气温
多次遍历数组
这可能是显而易见的，但是遍历数组两次/三次(只要少于 n 次)仍然是 O(n)。有时多次遍历数组可以帮助您解决问题，同时保持时间复杂度为 O(n)。
基本问题
如果你在学习这个话题，这些是需要练习的基本问题。
推荐练习题
这些是在你为题目学习并练习了基本问题后推荐练习的问题。
推荐课程
AlgoMonsterT3】
AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得终身访问。 今天加入七折优惠→
寻找编码面试:编码问题的模式
设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式，而不是背答案！ 现在获得终身使用权→
掌握编码面试:数据结构+算法
这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 19 个小时的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 结账→
