Skip to content

用于编码面试的数组备忘单

原文：https://www.techinterviewhandbook.org/algorithms/array/

简介

数组在连续的内存位置保存相同类型的值。在数组中，我们通常关心两件事——元素的位置/索引和元素本身。不同的编程语言以不同的方式实现数组，并且会影响对数组进行操作的时间复杂度。在 Python、JavaScript、Ruby、PHP 等语言中，数组(或 Python 中的 list)的大小是动态的，创建数组时不需要预先定义大小。因此，人们通常更容易在面试中使用这些语言。

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

优势

  • 用一个变量名存储多个相同类型的元素
  • 只要有索引，访问元素就很快，而不是像链表那样从头开始遍历。

缺点

  • 向数组中间添加元素或从数组中间移除元素很慢，因为需要移动剩余的元素来容纳新的/缺失的元素。一个例外是，如果要插入/移除的位置在数组的末尾。
  • 对于某些固定数组大小的语言，它在初始化后不能改变其大小。如果插入操作导致元素总数超过大小，则必须分配一个新的数组，并复制现有的元素。创建一个新数组并传递元素的行为需要 O(n)时间。

学习资源

常用术语

在处理涉及数组的问题时，您会看到一些常见术语:

  • 子数组-数组中连续值的范围。
    • 例如:给定一个数组[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 用于编码演示。 结账→

回到顶部