面试中需要熟知的数组知识

数组介绍

数组是计算机中一个很重要的数据结构，它使用的是一块连续的内存，而且数组中的元素是相同类型的。在数组中，我们通常关心两件事——元素的索引和元素本身。不同的编程语言在底层实现数组的方式不同，这会影响对数组操作的时间复杂度。在Python、JavaScript、Ruby、PHP等语言中，数组(Python中称为列表)的大小是动态的，在创建数组时不需要预先定义大小。在面试中使用这些解释型语言实现一段算法相比c/c++和java等编译型语言会更加方便。

数组是面试中最常见的数据结构之一，面试时很多其他类型的问题也经常会和数组结合，熟练掌握数组的操作对面试来说是必不可少的!

数组的优势

• 可以使用同一个变量名存储多个类型相同的元素。

• 访问元素的速度很快，只要知道元素的索引，就可以通过 O(1) 的时间复杂度立即访问到对应的元素，不像链表那样需要从头到尾去遍历。

数组的劣势

• 插入删除元素的操作比较慢，插入一个元素时，插入位置及其后面的元素需要向后移动。删除一个元素时，删除位置后面的元素需要向前移动。这就导致插入和删除的时间复杂度为O(n)，所以比较慢。

• 对于编译型语言，比如C++，数组的大小是固定的，初始化后不能更改其大小。如果插入操作导致元素总数超过数组的大小，那么必须重新分配一个新数组，并复制老数组元素到新数组中，再进行插入操作。创建一个新数组并且复制元素需要的时间复杂度是O(n)。

数组中常用的术语

• 子数组：数组中一块连续的子区间。举个例子，对于数组[1,5,8,4,3,2],[1,5,8]是它的一个子数组，[1,8,4]不是它的子数组。

• 子序列：在不改变数组元素顺序的基础上，对数组中某些元素进行删除操作，剩下的数组就是原数组的一个子序列。举个例子，对于数组[1,5,8,4,3,2],[1,8,4]是它的一个子序列，[1,4,8]不是它的子序列。

子数组属于子序列，但是子序列并非子数组。

数组的时间复杂度

使用数组时需要注意的一些问题

• 明确数组中如果存在重复元素对最终的结果是否会有影响。

• 在使用数据的索引访问元素时，切记不要越界。

• 能直接使用原数组的情况下切记不要使用数组切片或拼接两个不同的数组，对数组进行切片和拼接的时间复杂度为O(n)。

数组操作的一些边界情况

• 空数组的情况
• 数组中只有一个或两个元素的情况
• 数组中存在重复元素的情况

解决数组问题常见的方法

因为数组和字符串实现都是使用一块连续的内存(字符串是字符的数组)，所以这里的大多数方法都适用于解决字符串问题。

1. 滑动窗口

滑动窗口常用于多个子数组/子字符串问题。在滑动窗口中，两个指针通常朝同一方向移动，永远不会超过对方。这确保了数组中每个元素最多只被访问两次，时间复杂度仍然是O(n)。

2. 双指针

滑动窗口其实也是通过双指针来实现的，这里的双指针更通用，两个指针可以相互交叉，比如处理回文子串问题。甚至两个指针可以在不同的数组上，比如处理两个有序数组合并的问题。

3. 逆序遍历数组

有时候逆序遍历数组，会有意想不到的结果。

4. 二分查找

常常会有数组本身有序的情况，这时二分查找就很有用。或者题目本身对数组顺序没啥要求，这时可以尝试先排个序，再用二分查找试试。

5. 数组预处理

有些题目会涉及子数组的和或子数组的乘积，这个时候就可以预先把子数组的和或乘积保存起来备用。

6. 数组作为哈希表使用

在某些数组索引作为哈希表主键的情况下，可以直接使用数组替代哈希表。

7. 多次遍历数组

有些情况下可能需要多次遍历数组才能解决问题，遍历次数只要和n不在同一个数量级(比如两次或三次)，那么整体的时间复杂度依然是O(n)。