前言

众所周知，暴力解法能解决大多数问题，但是暴力解法的效率可谓是相当低，时间复杂度动辄O(n^n)，这样系统的运行时间将是无比的漫长，接下来，我将通过两道算法题带大家学习使用双指针来解决算法题。\

何为双指针？

双指针算法是一种利用两个指针在数据结构（如数组或链表）上协作遍历的策略，以高效地解决特定类型的问题。这种算法的核心在于通过两个指针的相对移动来扫描数据，从而达到诸如查找、删除、排序或优化遍历过程等目的。双指针主要分为以下两种常见模式：

1. 快慢指针（也称作追逐指针）：

   • 在这种模式下，一个指针（“快指针”）移动速度比另一个指针（“慢指针”）快，通常是一次移动多步。这种策略常用于检测循环的存在，如链表中的环检测问题，以及某些数据处理场景，如删除链表中的倒数第N个节点。

2. 对撞指针（也称作收缩窗口指针）：

   • 这种模式下，两个指针从数组或序列的两端开始，向中间移动，直到它们相遇或超越某个条件。这种方法广泛应用于数组中的目标和搜索、查找对称数、去除数组中的重复元素以及实现滑动窗口等场景。

双指针的应用

快慢指针（追逐指针）的应用

283. 移动零

• 简单

提示：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

 

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

解题思路

这题可利用追踪指针解答。定义两个指针i和j，分别从下标0开始。

• 当遇到0时，i继续寻找下一个非0，j则停留在值为0的下标处，等到i寻找到下一个非0，nums[i]和nums[j]替换，i和j继续往后遍历重复上述操作至结束；
• 当遇到非0时，nums[i]=nums[j]，i和j继续增加往后遍历。

解题代码

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    if (nums == null || (nums.length == 1))
        return;
    var j = 0;
    for (let i = 0; i < nums.length; i++){//遍历数组
        if(nums[i] !== 0) {
            var temp = nums[i];
            nums[i] = nums[j];
            nums[j++] = temp;
        }
    }
};

对撞指针（收缩窗口指针）的应用

11. 盛最多水的容器

• 中等

提示：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明： 你不能倾斜容器。

 

示例 1：

输入： [1,8,6,2,5,4,8,3,7]
输出： 49 
解释： 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入： height = [1,1]
输出： 1

 

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

解题思路

这题可利用对撞指针解答。

要想盛最多水，则两条线的x轴距离*两条线中的最低高度要最大

定义两个指针left和right，left从下标0开始递增，right从下标height.length-1开始递减。再定义一个最大容器面积maxArea，初始量为0。 进入循环，当左指针大于等于右指针时，退出循环。

• 循环内，将每一次得出的面积与maxArea比较，若更大，则替换；
• 再比较两个指针所在下标数组的值，更小(也就是更矮)的向中间收缩，如此反复，直至跳出循环。

解题代码

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let left = 0
    let right = height.length - 1
    let maxArea = 0
    while (left <= right) {
        let minNum = Math.min(height[left], height[right])
        let temp = (right - left) * minNum
        maxArea = Math.max(maxArea, temp)
        if (height[left] < height[right]) {
            left++
        } else {
            right--
        }
    }
    return maxArea
};

总结

双指针法的优势在于其能够简化逻辑、减少遍历次数，从而在很多情况下将算法的时间复杂度降低到O(n)。通过巧妙地设计指针的移动规则和停止条件，可以在一次遍历中完成原本可能需要多次遍历才能解决的任务。此外，双指针也可以应用于多种数据结构，不仅限于线性结构，还能在树等非线性结构中找到应用。