array

文档摘要

确保翻译不显得太生硬。确保翻译注释。这个文件是用Markdown格式写的。不要把它当作XML或HTML。不要翻译任何[!NOTE]、[!WARNING]、[!TIP]、[!IMPORTANT]或[!CAUTION]。不要翻译任何实体，如变量名、函数名、类名，或占位符如@@INLINECODEx@@或@@CODEBLOCKx@@，但保留它们在文件中。不要翻译任何URL或路径，但保留它们在文件中。请从左到右写输出。

确保翻译不显得太生硬。确保翻译注释。
这个文件是用Markdown格式写的。不要把它当作XML或HTML。
不要翻译任何[!NOTE]、[!WARNING]、[!TIP]、[!IMPORTANT]或[!CAUTION]。
不要翻译任何实体，如变量名、函数名、类名，或占位符如@@INLINE_CODE_x@@或@@CODE_BLOCK_x@@，但保留它们在文件中。
不要翻译任何URL或路径，但保留它们在文件中。
请从左到右写输出。

id: array
title: 编码面试数组速查表
description: 编码面试数组学习指南，包括练习题、技巧、时间复杂度和推荐资源
keywords:
[
数组编码面试学习指南,
编码面试数组技巧,
数组练习题,
数组实用技巧,
数组时间复杂度,
数组推荐学习资源,
]
sidebar_label: 数组
toc_max_heading_level: 2

引言

数组在连续的内存位置上存储相同类型的值。在数组中，我们通常关注两件事——元素的位置/索引以及元素本身。不同的编程语言在底层对数组的实现方式不同，这可能会影响你对数组进行操作时的时间复杂度。在一些语言中，比如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是数组长度，可以将该索引对应的值取负（减一）来表示该数字的存在。示例：第一个缺失的正整数、每日温度

多次遍历数组

这可能很显然，但两次或三次遍历数组（只要次数少于n次）仍然属于O(n)。有时候多次遍历数组可以帮助你在保持时间复杂度为O(n)的情况下解决问题。

必备题目

这些是备考本主题时必须练习的题目。