数组题目技巧总结（一）

数组题目介绍

数组是最基本的数据结构，题目设计范围广泛，可以是操作原数组、查找、排序等，也可以和贪心算法、动态规划、递归、二分法等算法结合，还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍直接在数组上操作的题目。

问题类型与技巧

1. 数组的变型操作：可以是数组元素中的旋转、交换、移动。

   这类题型比较多，最重要的方法是找规律，不管是一维数组还是二维数组，观察变化后的数组与原数组的差异，思考如何最方便的变换。常用的技巧可能有：翻转使用双指针交换、旋转可能会用到多次翻转、矩阵可能与转置有关、另外开辟一个数组空间来存储中间值或者结果值等。

2. 根据数组的下标，构造原地哈希。

   如果数组中的元素与下标有关系，则可以构造根据下标当成值的索引，快速找到某个值。

3. 数组的遍历问题。

   一维数组的遍历比较常规与简单，主要是二维数组可能会有不同的遍历方式，这种情况下多模拟，画图遍历几次，就知道大概怎么遍历。

经典题型

• 题目①螺旋矩阵

  这道题目主要是上述问题第三点，属于数组遍历的问题。题目是一个二维数组，因此可以通过画图模拟过程，再根据过程写代码。

• 题目②顺时针旋转矩阵

  这道题目主要是上述问题第一点，二维数组的旋转变型。二维数组比较抽象，可以画出如下图，发现变换与转置和逐行翻转有关系，而矩阵的转置就是遍历下三角矩阵，将其与上三角（下标互换）矩阵的元素交换位置。

• 题目③旋转数组

  数组上面的变型操作，一半而言都可以使用另一个数组空间来承接变换，但是如果要求在原数组上修改的话，优先考虑翻转或者分段翻转，或者局部交换位置。这道题就是经过了三次不同位置的翻转达到了旋转数组的效果。

• 题目④缺失的第一个正整数

  这道题目是上述问题第二点，可以通过构造原地哈希实现。因为题目的1～n与数组下标0～n-1刚好一一对应，可以使用下标指向某一个出现的数字。

• 题目⑤调整数组顺序使奇数位于偶数前面

  这道题也是对应上述问题第一点，变换数组。在原数组上不便于操作，我们可以构造一个新数组，承接变换后的结果，这样相当于直接赋值。