数组题目介绍

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

问题类型与技巧

  1. 数组与递归的问题

    常规的数组遍历肯定用不上递归，但是如果需要在数组中查找几个特定的元素，一般会用到递归。递归一般从数组开头作为入口，查找到某个元素，将该元素后续的子数组送入子问题中继续查找某个元素，直到找全符合条件的元素或者到达数组尾才结束递归。这其中还可能会涉及回溯与枝剪等算法。

  2. 数组与双指针的问题

    数组中一般不直接出现指针，我们将使用两个下标称之为双指针法。多用于两个数组的情况，当然一个数组也可以使用，比如控制滑动窗口、双指针交换元素位置等。

  3. 数组与二分法的问题

    在有序或者部分有序的数组中快速查找某个数，一般可以考虑二分法。在数组中划分左右端点，考虑中间值，然后移动左右端点，直到找到目标值。当然二分法也会有一些变体。

经典题型

  • 题目①数组中相加和为0的三元组

    在数组中求多元组可能会采用递归，但是三元组的话可以用双指针优化，因此这道题是属于上述问题的第二点。因为问题要求三元组内部有序，因此要对数组排序，在一个有序数组中操作。遍历数组元素作为三元组第一个变量，然后用双指针指向数组后续首尾当成另外两个变量，根据大小关系改变指针位置即可。 alt

  • 题目②寻找峰值

    这道题属于数组与二分法的结合问题。这道题的数组虽然不是有序或者部分有序，但是只要不断往上走就一定会找到波峰，因此可以使用二分法每次都往上走。 alt

  • 题目③二维数组中的查找

    这道题在二维数组中行列都是各自有序的，因此可以利用二分的思想，从左下角开始往上，每次大了就往上，小了就往右，知道查找到目标或结束。 alt

  • 题目④加起来和为目标值的组合

    这道题要求数组的全部符合条件的多元组合，因此需要使用递归，递归入口就是数组首和target，找到一个元素，target减去相应的值，并和剩余数组进入子问题，直到数组结束或者target为0结束递归。 alt

  • 题目⑤集合的所有子集

    这道题也是要求数组的全部多元子组合，可以递归处理，但是这里因为是求全部的子集，因此可以构造掩码映射，然后根据映射每次选取不同的元素作为集合，所以循环也可以解决。（用递归主要是不知道要循环多少次的时候） alt