前言

这次给大家带来的算法是双指针和二分法。

双指针

指针的思想不用多说，在我们日常的工作中是很常见的，比如我们写一个for循环遍历数组，那我们定义的变量 i 就是一个指向数组中每一项的指针；

双指针思想，顾名思义就是两个变量来指向两个节点，通过指针的不断移动找出我们想要的结果。

指针的思想很简单，但难点在于我们要如何去灵活运用指针的思想来解决问题。我们还是通过去解决实际问题，在实际问题中去优化我们的指针思想：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。

请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

输入： nums = [-1,0,1,2,-1,-4]
输出： [[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

对于这个题，题目描述不复杂，就是三数之和等于 0，那么就输出到我们的答案数组即可。最直观的做法，当然就是三重遍历，也就可以当做是三个指针，三个指针指向的三个数字如果和为 0，那么我们就给记录到答案数组中，最后遍历完成之后输出出去。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    var ans = []
    for(var i = 0;i < nums.length;i++) {
        for(var j = i + 1;j < nums.length;j++) {
            for(var k = j + 1;k < nums.length;k++) {
                if(nums[i] + nums[j] + nums[k] == 0) {
                    let arr = [nums[i],nums[j],nums[k]]
                    ans.push(arr)
                }
            }
        }
    }
    return ans
};

然后题目中，又提到了我们输出的数组不能重复，所以，那我们简单处理一下，用Set去一下重。

var threeSum = function(nums) {
    var ans = []
    var s = new Set()
    for(var i = 0;i < nums.length;i++) {
        for(var j = i + 1;j < nums.length;j++) {
            for(var k = j + 1;k < nums.length;k++) {
                if(nums[i] + nums[j] + nums[k] == 0) {
                    let arr = [nums[i],nums[j],nums[k]]
                    /* 我们想要通过Set去重，所以要确保如果是重复的数组，
                       变成字符串之后必须是一致的，所以要做一次排序 */
                    arr.sort((a,b) => a - b)
                    if(!s.has(arr.join(','))) {
                        ans.push(arr)
                        s.add(arr.join(','))
                    }
                }
            }
        }
    }
    return ans
};

以上就是三重循环的做法。思路还是比较清晰的，但这种暴力搜索的做法是无法通过验证的。

我们上面做法的主要问题在于：

• 三重遍历，时间复杂度直接飙到 O(N³)。
• 每一层遍历都是暴力搜索，那有没有什么逻辑可以让我们的搜索更有方向呢？

接下来，我们就尝试用双指针的思想来优化一下上面的算法。

题目中提到我们最终的答案数组的满足条件是nums[i] + nums[j] + nums[k] == 0， 那将这个式子做一下简单的移项处理nums[i] + nums[j] == - nums[k]， 是不是就可以将这个题目理解为，固定一个数（nums[k]），然后遍历剩余项，两数之和等于 - nums[k] 的问题呢？

如果我们的剩余项是一个排好序的数组（比如是一个从小到大的数组），那我们这时候如果用两个指针 (l 和 r) 分别指向数组的左右两端，那我们就可以根据两个指针所指向的两数之和 (sum) 进行判断：

• 如果 sum > - nums[k] , 那么说明我们目前两个指针指向的数字之和选大了，那就把右指针往左挪一挪，取个小点的数。
• 如果 sum < - nums[k] , 那么说明我们目前两个指针指向的数字之和选小了，那就把左指针往右挪一挪，取个大点的数。
• 如果 sum = - nums[k]， 那说明这两个指针是符合我们的条件的，可以推入答案数组。

整体思路：

根据上面的思路：

• 首先，我们对数组nums进行排序
• 然后，固定k指针，遍历剩余的数组，对剩余的数组采用双指针的思想，从左右两端进行遍历取值。当左指针和右指针相遇的时候，遍历结束。这样我们就可以将时间复杂度优化至 O(N²)
• 最后，还要考虑到数组的去重问题（去重问题的思路，我放在代码注释里）

下面就是我们优化后的代码啦：

var threeSum = function(nums) {
    var ans = []
    // 对数组进行排序，方便后面两数之和取值之后，与nums[k]比较，判断指针移动
    nums.sort((a,b) => a - b)  
    var s = new Set()
    for(var k = nums.length - 1;k >= 0;k--) {
        /* 因为我们每次固定一个nums[k]之后，会将包含nums[k]的所有数组都找出来，
           所以再次遇到相同数字直接跳过即可 */
        if(s.has(nums[k])) continue
        s.add(nums[k]) // 将遍历过的nums[k]记录下来
        let tmp = -nums[k]
        let l = 0
        let r = k - 1
        while(l < r) {
            if(nums[l] + nums[r] == tmp) {
                let arr = [nums[l],nums[r],nums[k]]
                ans.push(arr)
                // 对于重复的元素，我们在确保已经对它进行过验证的情况下，直接跳过
                while(l < r && nums[l + 1] == nums[l]) {
                    l++
                }
                while(l < r && nums[r - 1] == nums[r]) {
                    r--
                }
                l++
                r--
            }else if(nums[l] + nums[r] < tmp) {
                l++
            }else{
                r--
            }
        }
    }
    return ans
};

双指针思想，多用于我们对算法的优化，如果我们写出来的算法需要像上面题目那样有多层次的遍历，那么我们就可以尝试使用双指针的思想，利用左右两指针，一个从前往后走，一个从后往前走，两针相遇就结束这一轮遍历，只要算法逻辑设计合理，一定能大大降低我们算法的时间复杂度。

如果上面的题目理解之后，可以尝试自己来做一下这道题： 三数之和

以及这道非常类似的题目，可以尝试独立解答一下最接近的三数之和

二分法

二分查找，是一种对遍历算法进行优化处理的算法，它的具体操作就是，每次我都取数字合理范围内的中间值，也可以说是左右两个指针所涵盖范围的中间值，如果中间值符合题意，直接输出；不符合题意，再判断是左指针移动，还是右指针移动，缩小区间，再次取中间值，进行比较，重复进行上述步骤，直到找出最终答案。

我们对一个数组进行遍历操作，时间复杂度是O(N)，而如果我们是用二分法处理这个数组，那其实就相当于我们把这个 N 不断的除以 2，所以最后我们二分法的时间复杂度就可以优化为 O(LogN)。

二分法具体如何操作，我们看一个小时候大家都玩过的游戏：

猜数字，比如我给定数据范围是 1 - N,然后我会从中选择一个数字作为答案，你来猜我选的数字是多少，每次猜完之后，我会告诉你是大了还是小了。

对于这个游戏，我们就可以每次猜中间的数，再根据提示调整我们的数据范围就好了。

比如数据范围是1 - 10，最终答案是6.那么我们的二分过程就是：

1. 以 1 为左边界，10 为右边界，我们猜 5 ===》 小了
2. 以 5 为左边界，10 为右边界，取中间值，我们猜 7 ==》 大了
3. 以 5 为左边界，7 为右边界，取中间值，我们猜 6 ===》 猜中答案

上面就是我们二分法的一个简单应用。

然后我们来看看真正在算法题目中，二分法是以什么样的姿势出现的呢？

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例：

输入： nums = [3,4,5,1,2]
输出： 1
解释： 原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

我们最后要求的是数组中的最小元素，那么如果直接遍历数组，然后找到最小值，我们的时间复杂度就会来到O(N)，这并不符合题目要求。题目要求我们实现时间复杂度为 O(LogN) 的做法，那自然就是典型的使用二分查找了。

对于这个题目，我们可以将数组在坐标轴上进行复现，这样我们的处理会更加的直观：

题目条件中说到，原来是一个递增数组，之后通过旋转得到后来的数组：

通过上图，我们就可以发现，纵然这个数组发生了旋转，它也依然是有规律可循的。旋转后的数组分成了两个区间，而每个区间的数字在自身区间都是递增的，而右区间的所有数字都小于左边区间。我们要找的最小数字，就是要找右区间的第一个数字。

当我们采用二分法的时候，中间值mid是可能落在左区间也可能落在右区间的，因为我们最终是要求右区间的第一个点，所以我们就尽可能的将我们的区间往右区间去靠拢就好了。

如何判断我们的坐标点在右区间呢？这里我们定义两个指针（L和R），如果nums[mid] < nums[R] 的话，就说明我们 mid 所处的位置是右区间，为了取最小值，我们将右指针移动到mid的位置；如果nums[mid] > nums[R] 就说明mid落在了左区间，在左区间一定不会存在我们所要的答案，所以将做左指针移到mid + 1的位置。

当左右指针相遇之时，那么指针所指的数字就是我们所要求得的最小值。

最终将逻辑形成算法：

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    var l = 0
    var r = nums.length - 1
    // 如果数组并没有发生旋转，那么第一个数字就是最小值
    if(nums[r] > nums[l]) return nums[0]
    var mid = Math.floor((l + r) / 2)
    while(l < r) {
        if(nums[mid] < nums[r]) {
            r = mid
        }else{
            l = mid + 1
        }
        mid = Math.floor((l + r) / 2)
    }
    return nums[l]
};

以上就是二分法的具体实现步骤。二分法的思路不是很难，实质就是缩小取值区间，当区间缩小到极致的时候（也就是左右两指针相遇的时候），就能够得出我们的答案。二分法的难点在边界问题，边界到底如何去找，左右指针到底要不要mid + 1或者mid - 1，还是直接等于mid。

对于二分法的坑点，只有尝试了才知道边界问题的难处。所以建议可以先练习几道二分法的题目，然后自己感受一下找边界的问题，如果感觉确实这里有点模糊，可以推荐一下力扣大佬这部分的讲解： 二分法

最后

至此我们已经学习了DFS, BFS, 哈希表， 回溯剪枝， 双指针， 二分法这六种算法解题思路，此时我们再去力扣玩耍的话，已经可以去解一部分的题目了，当这几种算法熟练了之后就可以尝试打周赛了。

一入算法深似海，刷题之路一定是一个非常艰辛的过程，前方还有动态规划，贪心算法，记忆化搜索等等更加不易翻越的大山，不要畏惧，不要焦躁，我们还是慢慢来，只要我们是向前的，就够了。也许，在某个时候，我们回头看，就会发现，原来我们一直在路上，而且已经走了这么远了呀！