数组类型题目做前必看

前言

数组类型的题目一般是 给定一个数组nums,要求在数组中查找目标数target、组合其中的元素得到某个值、对该数组进行操作满足要求。
对于某些问题，通常会有一些通用的方法作为其中的一环甚至直接可以得到答案。在刷 leetcode 之前，可以先记住这些方法，有的放矢。

二分搜索

当题目中描述，数组为有序数组或者要求算法时间复杂度为 logn 时，首先要想到的就是二分法(binary search)。
首先要记住的是二分法的前提是针对有序数组的。
二分法的思想就是，定义数组的左右边界，left, right, 以及通过左右边界计算出的中间位置 mid，
通过 mid 位置的值来判断是否符合要求，假设满足题目中规定的要找出一个元素满足函数 g，那么二分搜索的结果就是满足函数 g 的最小元素，模版为:

const binarySearch = (nums) => {
    let l = 0
    let r = nums.length // 搜索范围为 [l,r)
    while (l < r) {
        let m = l + Math.floor((l - r) / 2)
        if (g(m)) {   // g(m) 可以理解为满足要求的条件
            r = m     // 缩小搜索范围为 [l, m)
        } else {
            l = m + 1 // 缩小范围为 [m+1, r)
        }
    }
}
复制代码

此模版对应的搜索范围为左闭右开区间，如果是封闭区间的话，可以参考这个模版:

const binarySearch = (nums) => {
    let l = 0
    let r = nums.length - 1 // 搜索范围为 [l,r]
    while (l < r) {
        let m = l + Math.floor((l - r) / 2)
        if (g(m)) {   // g(m) 可以理解为满足要求的条件
            r = m - 1     // 缩小搜索范围为 [l, m-1]
        } else {
            l = m + 1 // 缩小范围为 [m+1, r]
        }
    }
}
复制代码

有了这个二分搜索的模版，就可以解决一些数组的问题了，比如 leetcode35 就是完完全全的模版套用就可以得到答案，下面就让我们愉快的刷数组类型的题目吧！

备注

此文章会根据在刷题过程中遇到的相似的问题中不断总结，逐步更新，笔者的目标是总结出常规的套路，方便更好的刷题。加油吧，骚年！