【优选算法】双指针算法

一、双指针简介

常见的双指针有两种形式：对撞指针 和 快慢指针 。

对撞指针

也称左右指针，一般用于顺序结构中。

特点：一个指针在最左边位置，一个指针在最右边位置，两个指针逐渐往中间走，直到相遇或者错开就停止。

快慢指针

也称 前后指针， 其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

特点：通常用于处理 环形链表 或 数组 或者其他 出现循坏往复情况 的问题，最常用的方式是让慢指针每一次移动一位，让快指针每一次移动两位。

二、OJ题目

2.1 移动零

算法设计

根据题目的示例1分析，我们可以发现：

结果分为两个部分：一部分全是非零元素，一部分全是零

这两个部分将整个数组分块了，那我们就可以使用双指针来划分。

定义两个指针 cur 和 dest ，其中 cur 指针用来扫描数组，它的左边是已扫描的部分，右边是未扫描的部分；dest 指针充当非零元素部分和零元素部分的分界，而这两个部分又包含在已扫描部分中，因此操作的过程中数组被 cur 和 dest 分为三个部分：非零元素部分、零元素部分和未扫描元素部分。

当 cur 扫描完整个数组必会越界，此时操作就完成了，整个数组被 dest 分为两个部分：非零元素部分和零元素部分。

从以上分析可以看出，我们使用的是快慢指针来解决这道问题。

具体操作如下：

1. 先初始化双指针：cur 在下标为0的位置，dest 暂时不让它进入数组，给一个-1。（即 cur = 0, dest = -1）

2. 然后我们让 cur指针开始遍历扫描数组：当 cur 还未越界时，我们就判断一下 nums[cur] 这个元素是否为零：

1. 若不为零，我们就让 nums[dest+1] 和 nums[cur] 进行交换；

2. 若为零，就让 cur 继续扫描数组。

3. 当 cur 越界，就结束操作。

读者可以自行模拟以上操作，看看所得结果是否满足题目要求。

代码实现

public void moveZeroes(int[] nums) {
    int cur = 0, dest = -1;

    while (cur < nums.length) {
        if (nums[cur] != 0) {
            swap(nums,++dest,cur++);
        } else {
            cur++;
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

提交结果：

算法总结

这道题目的特点是 数组分块 ，因此以后我们刷题时遇到类似题目时，可以采用此题的算法思路结合题目具体细节来解决问题。

2.2 复写零

算法设计

我们采用快慢指针来解决这道问题：cur指针用于检查元素是否为零；dest指针用于复写操作。

具体如下：

1. 初始化双指针：cur 置于下标为0的位置，dest 初始化为-1；

2. 遍历数组进行复写操作：

1. 当 arr[cur] 不为零：将 arr[cur] 复写至 arr[dest+1]；

2. 当 arr[cur] 为零：进行两次 arr[++dest] = 0 操作。

3. 当 cur 越界，操作就结束。

但是，当我们根据示例1从前往后进行模拟复写操作时，会发现有些元素会被覆盖：

原数组中下标为2的元素2被覆盖了，这意味着往后再怎么复写这个答案都是错的，因为有数据丢失。

因此，按照从前往后的方法不可行，那从后往前呢？

我们观察示例1，可以发现最后一个复写的元素是4，那我们不妨将 cur 置于元素4，将 dest 置于数组最后位置

接下来从后往前模拟复写操作（思路一致，只不过方向不同，'+' 号改 '-' 号即可），

可以发现，结果正确，说明从后往前复写的方法是正确的。

那么这道题目的解题步骤就是：

1. 首先找到每一个测试用例的最后复写的元素

2. 然后进行复写操作。

那么问题来了，我们是通过观察示例1才得知最后复写的元素，计算机可不会观察。

那怎么找呢？

具体如下：

1. cur = 0, dest = -1；

2. cur 遍历数组：

1. 当 arr[cur] 不为零，dest++ 即可；

2. 当 arr[cur] 为零，dest += 2。

3. 在 cur++ 之前，我们首先要判断一下 dest 的位置是否越界（因为当 arr[cur] 是零时，dest 的位置经过操作后可能会越界：示例 [1,0,2,3,0,4] ）:

1. 若 dest == arr.length：此时复写的两个零的位置是 arr.length-1 和 arr.length，

由于 dest 等于 arr.length 时已越界，我们不管，只需要将 arr[arr.length-1] 改成0，

2. 然后再让 cur--，dest -= 2即可。

经过以上三步的操作，我们就可以找到每一个测试用例的最后复写的元素，接下来进行复写操作即可。

读者可自行模拟操作。

代码实现

public void duplicateZeros(int[] arr) {
    int cur = 0, dest = -1;
    int n = arr.length;

    // 1. 找到最后复写的数
    while (cur < n) {
        if (arr[cur] == 0) {
            dest += 2;
        } else {
            dest++;
        }
        // 判断dest位置是否越界
        if (dest >= n-1) {
            break;
        }
        cur++;
    }
    // 处理细节
    if (dest == n) {  // 导致这种情况必是因为arr[cur]为0
        // 只将arr[n-1]改成0即可
        arr[n-1] = 0;
        cur--;
        dest -= 2;
    }

    // 2. 从后往前复写
    while (cur >= 0) {
        if (arr[cur] != 0) {
            arr[dest--] = arr[cur--];
        } else {
            arr[dest--] = 0;
            arr[dest--] = 0;
            cur--;
        }
    }
}

提交结果

算法总结

这道题目需要转变一下思路，既然从前往后行不通，那就从后往前。其原因就是按原来的方法会有数据被覆盖，因此当以后遇到类似的题目，我们可以采用这道题目的思路。

2.3 快乐数

算法设计

由题目描述我们可以知道，验证快乐数操作是一直重复的：

1. 最终结果始终无限循环变不到1，

2. 最终结果是1（我们可以看作重复操作但结果一直是1）

对示例1进行模拟操作：

对于这种情况，我们可以使用 快慢指针 的方法解决这道题：

1. 初始化双指针：先将 slow 置为 n ，将 fast 置为 slow 后的元素（即经过一次操作后得到的数）；

2. 让 slow 每一次走一个位置，fast 每一次走两个位置；

3. 当两个指针相遇，判断所处位置的值：

1. 若所处位置的值为1，表示 n 是快乐数，返回 true；

2. 若所处位置的值不为1，表示 n 是快乐数，返回 false。

这种操作是不是有点似曾相识的感觉？本题与 判断链表中是否有环 一题的解法是如出一辙。

读者可以自行模拟以上操作。

代码实现

public boolean isHappy(int n) {
    int slow = n, fast = isHappyNum(n);

    while (slow != fast) {
        slow = isHappyNum(slow);
        fast = isHappyNum(isHappyNum(fast));
    }

    return (slow == 1) ? true : false;
}

private int isHappyNum(int n) {
    int temp = 0, ret = 0;
    while (n > 0) {
        temp = n % 10;
        n /= 10;
        ret += temp * temp;
    }
    return ret;
}

提交结果

算法总结

本题的特点是出现循环、重复某个操作，因此采用 快慢指针 的方法来解决，以后遇到此类相似问题，我们也可以采用这种算法思路来解决。

2.4 盛最多水的容器

算法设计

根据题目描述，我们需要返回面积的最大值，

面积计算方式如下：S = (right - left) * min( height[left], hright[right] )

最简单的解法就是将所有可能的面积都求出来，然后比较哪一个最大，返回最大的面积即可。

解法一：暴力枚举

1. 使用两个指针，left 遍历数组，每次固定一个数，然后 right 逐一遍历数组，将每一个数与 left 所固定的数组合并求出面积；

2. 当 right 遍历完数组，left 再向后走一位，right 回到 left 的位置重新开始遍历操作。

3. 将得到的最大面积返回即可。

但是，当我们把代码提交，可以发现这种解法会超时。

我们从面积计算公式来看：

v = h (高) * w (宽)

1. 当 h 最高且 w 最宽时，整个面积是最大的；

2. 当 h 不变且 w 减少时 或者 当 h 减少且 w 减少时，面积都不是最大的。

我们能否从两端开始寻找呢？当找到最高的 h ，w 也是最大的。

解法二：双指针（对撞指针）

1. 先初始化指针：将 left 置于下标为0的位置，将 right 置于数组最后位置；

2. 用一个变量 maxArea 存放最大面积，计算以 left 和 right 为两边的容器的面积并更新 maxArea

3. 接下来让 left 和 right 逐渐往中间走：判断左右两条边那个更短，若左边更短，left ++；若右边更短，right --，计算新的面积并更新 maxArea

4. 当 left 和 right 相遇，返回结果即可

读者可以自行模拟以上操作

代码实现

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int v = 0;
    int maxArea = 0;

    // 双指针从两边到中间找容积最大的
    while (left < right) {
        v = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, v);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    //  返回最大容积
    return max;
}

算法总结

这道题目使用 对撞指针 的原因是需要从数组的两边往中间进行遍历，往后若遇到相似情形可以借鉴该题目的解法。

2.5 有效三角形的个数

算法设计

解法一：暴力枚举（会超时）

最容易想的解法就是将所有的三元组全部列出来，然后看看哪些能够构成三角形。

转换成代码就是需要三层循环来实现，时间复杂度能够达到 O（N³）。

最开始让 i 置于下标为0的位置，j 位于 i+1 位置，k 位于 j+1 位置，然后逐一遍历判断。

很显然，这种解法太耗时，我们需要优化一下。

解法二：双指针（排序 + 对撞指针）

我们知道，构成三角形的条件是：任意两边之和大于第三边，

我们这个解法之所以用时长是因为我们需要找三个数，

如果我们将问题转化成：找到两个数他们的和大于一个固定的数，那么我们就可以减少时间的消耗，从而提高效率。

我们可以这样做：将数组排列成有序数组（利用有序数组的单调性），然后直接找到最大的数（固定的数），再在前面的区间中找到两个数的和大于该固定的数，再固定下一个最大的数循环操作。

具体步骤：

1. 先将数组排序。

2. 我们固定一个 最大数 i ，再在 [0, i - 1] 这个区间中找出两个和大于该最大数的数（二元组），

3. 我们定义双指针 left = 0，right = i - 1，则在区间 [left, right]中：

1. 若 nums[left] + nums[right] > nums[i] ：

· 由于 left 是区间内最小的数，left + right 的值都大于 i 了，那区间内其他数肯定也满足要求（即区间 [left + 1, right]）。

· 计算满足条件的三元组的个数：right - left。

· 此时 right 位置元素的所有情况已经考虑完了，我们需要 right--，继续下一轮的操作。

2. 若 nums[left] + nums[right] <= nums[i] ：

· 由于 right 是区间内最大的数，left + right 的值都小于等于 i 了，那区间内其他数肯定也是小于或等于 i 的（即区间 [left, right - 1]）。

· 此时将 left++，进入下一轮的操作。

4. 操作结束后，返回统计到的三元组的个数即可。

该解法的时间复杂度是 O（N²）。

读者可以通过画图工具自行模拟以上操作。

代码实现

public int triangleNumber(int[] nums) {
    int ret = 0, left = 0, right = 0, n = nums.length;

    // 1.对数据进行排序
    Arrays.sort(nums);

    // 2.统计有效的三元组的个数
    for (int i = n - 1; i >= 2; i--) {
        left = 0; right = i - 1;
        while (left < right) {
            if (nums[left] + nums[right] > nums[i]) {
                ret += right - left;
                right--;
            } else {
                left++;
            }
        }
    }

    return ret;
}

算法总结

这道题目中利用了有序数组的单调性得以实现效率的提升，有时候 单调性 是很重要的特性，在以后遇见的题目中要时刻留意是否有单调性这一特性。

2.6 查找总价格为目标值的两个商品（两数之和）

算法设计

解法一：暴力枚举

最简单的做法就是使用两层循环遍历数组找到两个数，但是会超时。

解法二：对撞指针

注意到数组是升序排列的数组，我们可以使用对撞指针来解决。

步骤如下：

1. 初始化双指针：left = 0，right = n - 1（这里的 n 是数组的长度）。

2. 当 left 小于 right 的时候，就一直循环以下操作：

1. 当 price[left] + price[right] > target：

· 由于 left 是区间 [left, right] 中最小的数，最小的数与区间内最大的数 right 相加都大于 target 了，那么比 left 还大的数与 right 相加肯定更大了。因此没有必要从区间 [left + 1, right] 中查找了，我们直接让最大的数 right-- 即可。

2. 当 price[left] + price[right] < target：

· 由于 right 是区间 [left, right] 中最大的数，最大的数与区间内最小的数 left 相加都小于 target 了，那么比 right 还小的数与 left 相加肯定更小了。因此没有必要从区间 [left , right - 1] 中查找了，我们直接让最小的数 left++ 即可。

3. 当 price[left] + price[right] == target：

· 找到目标数，我们返回结果即可。

3. 若操作结束都没有返回结果，说明数组中不存在满足要求的数，返回 null。

代码实现

public int[] twoSum(int[] price, int target) {
    int n = price.length, left = 0, right = n - 1;
    
    // 双指针遍历数组查找
    while (left < right) {
        if (price[left] + price[right] > target) {
            right--;
        } else if (price[left] + price[right] < target) {
            left++;
        } else {
            return new int[] {price[left] , price[right]};
        }
    }
    
    return null;
}

算法总结

我觉得这道题目是很有代表性的一道题目，经典的按照三种不同的情况来讨论，细节问题不多。后面还会有题目有更多细节需要处理。

2.7 三数之和

算法设计

解法一：排序 + 暴力枚举 + set 去重

这个代码需要使用三层循环来寻找三元组，是比较耗时的解法。

解法二：排序 + 双指针

整体思路和两数之和的思路差不多，只不过有些细节需要处理。

我们可以将三个数问题转化成两个数问题：

先固定一个数 a ，在剩下的数中找到和为 -a 的两个数，这样一来就转化为两数之和问题了。

题目要求 “不重复”，因此我们需要对满足条件的三元组进行“去重操作”。

具体步骤：

1. 对数组进行排序。

2. 先固定一个数 a ，在剩下的数中找到和为 -a 的两个数（使用对撞指针 left 和 right）：

· 若 nums[left] + nums[right] > -a：

直接让 right --

· 若 nums[left] + nums[right] < -a：

直接让 left ++

· 若 nums[left] + nums[right] == -a：

记录下该三元组，然后缩小范围继续下一轮的操作（left ++，right --）

3. 当操作完成，返回最终结果即可。

处理细节问题：

1. left 和 right 的去重操作：

在缩小范围之后，left 和 right 下一个位置的数可能会与之前的数重复，这时候我们需要判断一下是否与之前所处位置的数相等，若相等就再走一步（即再执行一次 left ++ 和 right --）。当然也不能一直执行，需要确保不越界（即 left < right ）才可以继续执行，否则就停止。

2. 固定的第三个数 a 的去重操作：

因为我们的 a 也是在遍历数组的，每固定一个数就开始一轮双指针查找。如果固定的数 a 重复的话，查找得到的三元组也会重复，这样就不符合题意了。因此，我们需要对 a 也进行去重操作，同时 i 也不能越界。

代码实现

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    int i = 0, left = 0, right = 0;
    int n = nums.length;
    
    // 1. 对数组进行排序
    Arrays.sort(nums);
    
    // 2. 使用双指针算法寻找三元组
    // 固定数
    while (i < n) {
        left = i + 1; right = n - 1;
        int t = -nums[i];
        // 在 [left, right] 范围内寻找和为t的两个数
        while (left < right) {
            if (nums[left] + nums[right] > t) {
                right--;
            } else if (nums[left] + nums[right] < t) {
                left++;
            } else {
                // 将找到的三元组通过Arrays集合类的asList方法转换为List，然后用尾插法插入ret
                ret.add(Arrays.asList(nums[i],nums[left],nums[right]));
                // 缩小下一次寻找的范围
                left++;
                right--;
                // 对left和right进行去重操作（注意不要越界）
                while (left<right && nums[left-1] == nums[left]) {
                    left++;
                }
                while (left<right && nums[right+1] == nums[right]) {
                    right--;
                }
            }
        }
        // 对i进行去重操作
        i++;
        while (i<n && nums[i-1] == nums[i]) {
            i++;
        }
    }
    
    // 3. 返回最终结果
    return ret;
}

算法总结

本题是由经典的 “求两数之和” 题目衍生而来的，其解题的核心仍然是利用双指针。

2.8 四数之和

算法设计

解法一：排序 + 暴力枚举 + set去重

和上一道题目一样，不过这次多了一层循环，即需要四层循环。

解法二：排序 + 双指针

这道题目我们可以沿用上一道题目 “三数之和” 的思路，先把四个数问题转化成三个数问题，再将三个数问题转化为两个数问题。

具体步骤：

1. 依次固定一个数 a ，在剩下的数中找到三个数和为 t - a。

2. 再依次固定第二个数 b ，在剩下的数中找到两个数和为 t - a - b。

3. 返回最终结果即可。

细节处理：

这道题目同样涉及到去重操作，因此我们也需要对固定的数 a、b，以及双指针 left 和 right 进行去重操作。

代码实现

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> ret = new ArrayList<>();
    int i = 0, j = 0, left = 0, right = 0;
    int n = nums.length;

    // 1. 将数据排序
    Arrays.sort(nums);

    // 2. 使用双指针算法
    while (i < n) {
        // 特殊情况处理
        if (target<0 && nums[0]>=0) {
            return ret;
        }
        // 找到三个数，和为target - nums[i]
        j = i + 1;
        // 使用long类型防止数据溢出
        long t1 = target - nums[i];
        while (j < n) {
            long t2 = t1 - nums[j];
            left = j + 1;
            right = n - 1;
            // 找到两个数，和为target - nums[i] - nums[j]
            while (left < right) {
                if (nums[left] + nums[right] > t2) {
                    right--;
                } else if (nums[left] + nums[right] < t2) {
                    left++;
                } else {
                    ret.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    // 缩小搜寻范围
                    left++;
                    right--;
                    // 对left和right进行去重操作
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
            // 对j进行去重操作
            j++;
            while (j < n && nums[j] == nums[j - 1]) {
                j++;
            }
        }
        // 对i进行去重操作
        i++;
        while (i < n && nums[i] == nums[i - 1]) {
            i++;
        }
    }

    // 3. 返回最终结果
    return ret;
}

算法总结

再次体现了 “两数之和” 这道经典题目的重要性~~

完