你敢学我就敢教 | 数组的四个经典算法

（一）线性枚举

学习线性枚举前，我们先来看个例题：精准空降链接

概念

       枚举的概念就是把满足题目条件的所有情况都列举出来，然后一一判定，从而找到最优解的过程。线性枚举一般是发生在顺序表上（注意这里的顺序表不一定有序，只是代表内存连续的意思），例如我们求一个数组中的最大值，可以通过遍历数组，对每个数进行访问和判定，从而找到最大值，这种就是最朴素的枚举算法。

例题

分析

       这个题目，最朴素的思路就是枚举递增的四个下标，然后判断是否满足题目中给定的条件，如果满足则计数器 +1，最后返回计数器，这种思路是最容易想到的，也就是传说中的暴力算法，由于枚举的过程中是顺序遍历数组的，所以也叫 线性枚举。
       容易得知，这种做法的算法时间复杂度是 O(n^4)，对于 n ≥ 50 的情况已经不堪重负了。

优化

       那么如何进行优化呢？O(n^3) 的时间复杂度比较好想，确定中间两个下标 (j, k)，然后分别确定左边的 i 和 右边的 l，利用乘法原理相乘，再累加就能得到答案了。这里我们来说说 O(n^2) 的算法。
       用一个 cnt 数组来记录以 j 作为中间那个数的 1 3 2 的三元数对，其中 j 是中间那个最大的数的下标：

     a[ j ] < a[ l ] 时， a[ l ] 扮演的是四元组的第四个数，那么就可以将 cnt[ j ] 累加到结果 ans 中，并且用 x 来记录，到目前为止，比 a[ l ] 小的数的个数，那么这种情况下 x 自然要自增。
    a[ j ] > a[ l ] 时，a[ l ] 扮演的是三元组 1 3 2 的第三个数，而我们之前已经统计出小于 a[ l ] 的数是 x 个，自然满足 1 3 2 这样的三元数对的数目就是 x，把它累加到 cnt[ j ] 上即可。

    最后返回 ans 就是所有统计出来的 满足 a[ i ] < a[ k ] < a[ j ] < a[ l ] 的四元组的个数了。代码很简洁，可以反复观摩。

（二）二分枚举

学习二分枚举前，我们先来看个例题：精准空降链接

概念

       二分枚举和线性枚举的区别就是：可以用折半的方法的对数据进行可行性判定，从而可以通过对数的时间复杂度，求解出问题的解。当然，二分枚举的要求是这个顺序表必须是有序表（即必须满足单调性，可以是单调递增、单调递减、单调不增、单调不降）。

       二分枚举本身的逻辑比较简单，但是一个题是否能够用二分来解决，是需要通过不断的训练和刷题锻炼出来的。

例题

分析

       但凡遇到求最大的最小值，或者最小的最大值，都可以优先想到用二分来枚举答案，然后对答案进行可行性判定。这个题如果不用二分枚举，我们可以从将 val 从 1 开始枚举，直到 100000000，写一个 check 函数，函数的功能就是返回一个布尔值，判定一个数组 nums 是否能够分成 m 组，并且每组的元素和不大于 val，如下：

优化

       如果这个 check 函数的作用能够看懂，那么相比你应该能够想到 val 是满足单调性的，也就是 val 越大， check 能够通过的概率也就越大，所以我们的目的就是找到 val 的临界值，如果用线性枚举的方式，就是 for 循环枚举枚举 val 的值，然后 check 判断可行性，很明显这样的算法时间复杂度很高，但是如果用 二分的方式去枚举 val 的值，然后用 check 来判断可行性，就把枚举的时间复杂度大大降低了。
       l 和 r 表示 val 的左右边界， ans 代表最终我们找到的那个最小的满足条件的答案。那么寻找 l 和 r 的中点，进行 check 判定，如果满足条件，则 mid 必然是一个可行解，存储到 ans 中，然后再去判断 [l, mid) 这个左闭右开区间中，是否有更小的满足条件的值，于是右区间就变成了 mid - 1；否则，就必须要去 (mid, r] 这个区间中找了。

       最终， ans 存储下来的一定是我们的最优解。

（三）双指针

学习双指针前，让我们先来看个例题：精准空降链接

概念

       双指针一般也是在有序数组上进行枚举的算法，对于一个有序表，先定义左右两个指针，分别从有序表的两端往中间靠拢，从而不断找到最优解、或者累加可行解的过程。

例题

分析

       学过线性枚举以后，最直白的想法就是直接枚举两个下标，然后对两者值的和进行如下判定，满足条件的进行计数，但是这种做法，时间复杂度 O(n^2)：

优化

        我们可以单独实现一个 countLessThan 函数，来计算数组中小于等于 value 的数对的个数，然后调用两次，相减即可（类似 部分和 的算法思想）。

        而对于一个有序数组，求多少个数对满足它们的和小于等于 value，就可以用双指针来求解，初始化两个指针 l = 0，r = n-1，如果 nums[l] + nums[r] 小于等于 value，则以 l 开头的数对数目就是 r - l，累加到 ans 中，左指针 + 1；否则，右指针 -1；

       最后返回 ans，就是我们要求的解了。

（四）哈希表

学习哈希表，那么我们先来看个例题：精准空降链接

概念

       哈希表作为一个经典的数据结构，是利用数组来进行实现的，当然底层原理比较长，这里就先不做介绍了，后续可以专门开个章节来讲。python 中的字典，底层实现就是哈希表，所以能够做到快速的增删改查。

例题

分析

       顺序枚举每一个数，每次枚举一个数，就把它插入到哈希表 index 中，而下次查找的时候，则通过 target - nums[i] 去查，如果能够查到，则必然存在两个数相加等于 target。
       但是，光找到这个数是不够的，还需要知道两者的下标，所以插入的时候，值作为下标即可。也就是插入的键值对是 （nums[i], i），也就是建立了一个反差表。

       好啦，如果你觉得这些内容对你有用，麻烦给我的文章或者视频点上一个赞吧，这样也会更好的激励我创作出更多优质的内容，予人玫瑰🌺，手留余香，谢谢~~