算法总结 | 技术面试手册 | tech-interview-handbook 中文文档

引言

数组在连续的内存位置存储相同类型的值。在数组中，我们通常关注两个问题 - 元素的位置/索引以及元素本身。不同的编程语言在底层实现数组时有所不同，这可能会影响你对数组进行操作的时间复杂度。在像Python、JavaScript、Ruby、PHP这样的某些语言中，数组（或Python中的列表）大小是动态的，创建数组时不需要预先定义大小。因此，使用这些语言进行面试时通常更容易。

数组是面试中遇到的最常见的数据结构之一。询问其他主题的问题也可能涉及数组/序列。掌握数组对于面试至关重要！

优点

用单个变量名存储同一类型的多元素
只要你有索引，访问元素就很快，因为与需要遍历头部的链表相比。

缺点

在数组中间添加或删除元素很慢，因为其余元素需要移动以容纳新/缺失的元素。如果插入/删除的位置在数组末尾，则例外。
对于某些数组大小固定的语言，初始化后不能更改其大小。如果插入导致元素总数超过大小，必须分配新的数组，并将现有元素复制过来。创建新数组并传输元素的时间复杂度为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 次）仍然是 O(n)。有时多次遍历数组可以帮助你在保持时间复杂度为 O(n) 的同时解决这个问题。

基本问题

如果你正在为这个主题学习，这些是必须要练习的基本问题。

引言