数组题目技巧总结（五）

数组题目介绍

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

问题类型与技巧

1. 数组与哈希表的问题

   最常见的数组与哈希表结合就是使用哈希表统计数组元素出现的频率，或者去重等任务，一般来说直接使用一个哈希表可以解决。

2. 数组与二叉树的问题

   二叉树遍历的结果需要存储在数组中，有时候需要在二叉树中查找的结果也会存储在数组中，也能根据数组还原构建二叉树，此时更多遵循二叉树的遍历规则。

3. 数组与栈或队列的问题

   有时候涉及先进先出或者先进后出的时候，需要用到栈或者队列。

经典题型

• 题目①数组中只出现一次的数字

  这道题是数组与哈希表结合，使用哈希表统计数组中数字的次数，然后找出哈希表中次数为1的两个数字即可。

• 题目②最长无重复子数组

  这道题是用哈希表保证滑动窗口内部无重复元素，一旦出现重复则需要移动滑动窗口。

• 题目③重建二叉树

  数组与二叉树结合的问题，二叉树的前序遍历结果与中序遍历结果存在数组中，需要知道对于二叉树的前序遍历，序列的第一个元素必定是根结点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根结点将二叉树分成了左右子树两个部分，然后遵循二叉树的遍历即可重建构建二叉树。

• 题目④数组中出现次数超过一半的数字

  使用哈希表统计数组中各个不同数字出现的次数，找出出现次数大于数组长度一般的数字。

• 题目⑤两数之和

  使用哈希表记录之前出现过的数字，便于快速找到与当前遍历元素匹配的另一个元素的位置。