28.md

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

> 原文:[https://www.techinterviewhandbook.org/algorithms/array/](https://www.techinterviewhandbook.org/algorithms/array/)

<header>

## 简介[](#introduction "Direct link to heading")

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

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

**优势**

*   用一个变量名存储多个相同类型的元素
*   只要有索引，访问元素就很快，而不是像[链表](/algorithms/linked-list/)那样从头开始遍历。

**缺点**

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

## 学习资源[](#learning-resources "Direct link to heading")

*   读物
    *   [数据结构中的数组:什么是数组运算](https://www.guru99.com/array-data-structure.html)，Guru99
*   录像
    *   [阵列](https://www.coursera.org/lecture/data-structures/arrays-OsBSF)，加州大学圣地亚哥分校

## 常用术语[](#common-terms "Direct link to heading")

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

*   子数组-数组中连续值的范围。
    *   例如:给定一个数组`[2, 3, 6, 1, 5, 4]`，`[3, 6, 1]`是一个子数组，而`[3, 1, 5]`不是子数组。
*   子序列——通过删除一些元素或不删除任何元素，而不改变剩余元素的顺序，可以从给定序列中导出的序列。
    *   例如:给定一个数组`[2, 3, 6, 1, 5, 4]`，`[3, 1, 5]`是一个子序列，但是`[3, 5, 1]`不是一个子序列。

## 时间复杂度[](#time-complexity "Direct link to heading")

| 操作 | 大 O | 注意 |
| --- | --- | --- |
| 接近 | O(1) |  |
| 搜索 | O(n) |  |
| 搜索(排序数组) | O(log(n)) |  |
| 插入 | O(n) | 插入需要将所有后续元素向右移动一位，这需要 O(n) |
| 插入(在末尾) | O(1) | 不需要移动其他元素的特殊插入情况 |
| 去除 | O(n) | 移除需要将所有后续元素左移一位，这需要 O(n) |
| 移除(在最后) | O(1) | 不需要移动其他元素的特殊移除情况 |

## 面试时要注意的事情[](#things-to-look-out-for-during-interviews "Direct link to heading")

*   澄清数组中是否有重复值。重复值的存在会影响答案吗？它使问题更简单还是更难？
*   当使用索引迭代数组元素时，注意不要越界。
*   请注意在代码中分割或连接数组。通常，分割和连接数组需要 O(n)时间。在可能的情况下，使用开始和结束索引来划分子数组/范围。

## 拐角情况[](#corner-cases "Direct link to heading")

*   空序列
*   具有 1 或 2 个元素的序列
*   具有重复元素的序列
*   序列中的重复值

## 技巧[](#techniques "Direct link to heading")

注意，因为数组和字符串都是序列(字符串是字符数组)，所以这里的大多数技术都适用于字符串问题。

### 滑动窗口[](#sliding-window "Direct link to heading")

掌握适用于许多子数组/子串问题的[滑动窗口技术](https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems)。在滑动窗口中，通常向同一方向移动的两个指针永远不会互相超越。这保证了每个值最多只被访问两次，时间复杂度仍然是 O(n)。例子:[无重复字符的最长子串](https://leetcode.com/problems/longest-substring-without-repeating-characters/)，[最小尺寸子阵列总和](https://leetcode.com/problems/minimum-size-subarray-sum/)，[最小窗口子串](https://leetcode.com/problems/minimum-window-substring/)

### 两个指针[](#two-pointers "Direct link to heading")

两个指针是滑动窗口的一个更一般的版本，指针可以互相交叉，可以在不同的数组上。例子:[排序颜色](https://leetcode.com/problems/sort-colors/)，[回文子串](https://leetcode.com/problems/palindromic-substrings/)

当您有两个数组要处理时，通常每个数组有一个索引(指针)来遍历/比较这两个数组，相关时递增其中一个指针。例如，我们使用这种方法来合并两个排序后的数组。例子:[合并排序后的数组](https://leetcode.com/problems/merge-sorted-array/)

### 从右侧[穿越](#traversing-from-the-right "Direct link to heading")

有时你可以从右边开始遍历数组，而不是传统的从左边开始。例子:[每日气温](https://leetcode.com/problems/daily-temperatures/)，[可见排队人数](https://leetcode.com/problems/number-of-visible-people-in-a-queue/)

### 排序数组[](#sorting-the-array "Direct link to heading")

数组是排序的还是部分排序的？如果是的话，某种形式的二分搜索法应该是可能的。这通常也意味着面试官在寻找比 O(n)更快的解决方案。

你能给数组排序吗？有时，首先对数组进行排序可能会大大简化问题。显然，如果需要保持数组元素的顺序，这是行不通的。例子:[合并间隔](https://leetcode.com/problems/merge-intervals/)，[非重叠间隔](https://leetcode.com/problems/non-overlapping-intervals/)

### 预计算[](#precomputation "Direct link to heading")

对于涉及子阵列的求和或乘法的问题，使用散列或前缀/后缀和/积的预计算可能是有用的。例子:[除自身数组的乘积](https://leetcode.com/problems/product-of-array-except-self/)，[最小子数组和](https://leetcode.com/problems/minimum-size-subarray-sum/)， [LeetCode 问题标注“前缀-和”](https://leetcode.com/tag/prefix-sum/)

### 作为散列关键字的索引[](#index-as-a-hash-key "Direct link to heading")

如果给你一个序列，而面试官要求 O(1)空间，那么可以用这个数组本身作为哈希表。例如，如果数组只有从 1 到 N 的值，其中 N 是数组的长度，则对该索引处的值求反(减一)以指示该数字的存在。例子:[第一次不见正](https://leetcode.com/problems/first-missing-positive/)，[每日气温](https://leetcode.com/problems/daily-temperatures/)

### 多次遍历数组[](#traversing-the-array-more-than-once "Direct link to heading")

这可能是显而易见的，但是遍历数组两次/三次(只要少于 n 次)仍然是 O(n)。有时多次遍历数组可以帮助您解决问题，同时保持时间复杂度为 O(n)。

## 基本问题[](#essential-questions "Direct link to heading")

如果你在学习这个话题，这些是需要练习的基本问题。

*   [两笔总和](https://leetcode.com/problems/two-sum/)
*   [买卖股票的最佳时机](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
*   [除自身以外的数组乘积](https://leetcode.com/problems/product-of-array-except-self/)
*   [最大子阵列](https://leetcode.com/problems/maximum-subarray/)

## 推荐练习题[](#recommended-practice-questions "Direct link to heading")

*这些是在你为题目学习并练习了基本问题后推荐练习的问题。*

*   [包含重复的](https://leetcode.com/problems/contains-duplicate/)
*   [最大乘积子阵列](https://leetcode.com/problems/maximum-product-subarray/)
*   [在旋转排序数组中搜索](https://leetcode.com/problems/search-in-rotated-sorted-array/)
*   [3 总和](https://leetcode.com/problems/3sum/)
*   [盛水最多的容器](https://leetcode.com/problems/container-with-most-water/)
*   [滑动窗口最大值](https://leetcode.com/problems/sliding-window-maximum/)

## 推荐课程[](#recommended-courses "Direct link to heading")

### [AlgoMonster](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)[T3】](#algomonster "Direct link to heading")

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得**终身访问**。 [**今天加入七折优惠→**](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)

### [寻找编码面试:编码问题的模式](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)[](#grokking-the-coding-interview-patterns-for-coding-questions "Direct link to heading")

设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。**学习和理解模式，而不是背答案！** [**现在获得终身使用权→**](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)

### [掌握编码面试:数据结构+算法](https://fxo.co/DQpY)[](#master-the-coding-interview-data-structures--algorithms "Direct link to heading")

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 **19 个小时**的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 [**结账→**](https://fxo.co/DQpY)

</header>