双指针算法之左右对撞指针

小羽

3 minute read

在上一篇博文中，我们讨论了Java中指针的定义和使用。这篇文章我们就来聊一聊一种在数组和链表中很常见的算法——双指针算法。

I. 定义

双指针是指在遍历集合中的对象是，不仅仅采用单个指针进行访问，而是使用两个指针，以不同的方式对集合进行扫描从而达到相应目的的算法。一般来说，双指针的扫描方式分为两种：一种是两个指针按照相反的方向进行扫描，直到两个指针相撞为止，这类算法被称作左右对撞指针算法；另一种是两个指针按照相同的方向进行扫描，但是运动的条件不相同，在这种状况下往往一个指针走的相对快，另一个相对慢，所以这类算法被成为快慢指针算法。这篇文章专门讲解左右对撞指针，而下篇博文会专门来讲解快慢指针。

II. 分类

  1. 左右对撞指针
  2. 快慢指针

III. 左右对撞指针

a. 定义

左右对撞指针通常在有序数组（sorted array）中被使用。一般将左侧的指针定义为左指针（left），右侧的指针定义为右指针（right），然后两个指针从两头向中间进行数组的遍历。当左右指针碰撞时，也就是left>right时，停止遍历。

Note: 左右对撞指针适用于有序数组（sorted array）。所以在遇到有序数组时，我们应当第一个想到用左右对撞指针来解决问题。当然，在无序数组中，此方法也有应用。

b. 实现方法

实现左右对撞指针算法，通常分为以下几个步骤：

  1. 对无序数组进行排序。
  2. 将左右指针分别指向数组的左右两端
  3. 使用while循环进行遍历，当左指针和右指针相撞时，停止。
  4. 设置左右两个指针的移动条件以及移动方式
  5. 记录结果

c. 经典习题

1) Container With Most Water（Leetcode 11)

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

avatar

这道题目的意思是输入一个无序数组，计算最大的长方形水箱面积。数组的index为长方形的长，数组中每个对象的值为长方形的宽。长方形的面积等于长乘以左右两个对象值中较小的那一个。

这道题目是一个典型的用双指针来解决的题目（虽然输入数组为无序数组）。解题思路是这样的，我们在数组的两端设置两个指针，并计算出所对应的面积且保存下来。然后我们移动指向更小的值的指针（如果是左指针就向右移一位，如果是右指针则向左移一位），因为只有移动指向更小值的指针所改变的面积才可能大于改变前的面积。（更大值的的对象在计算面积时并没有被使用，如果移动这个指针，当它所指的对象变得更大时，这个值还是不会被用到，指向更小值时，则面积必然会变小）。

解题步骤如下：

  1. 设置左右指针为数组的左右两端的index,设置area变量用于储存结果。
int area = 0;
int left = 0;
int right = height.length-1;
  1. 使用while循环，当left<right时停止循环。
while(left < right){
			...
}
  1. 计算出当前指针指向的长和宽所对应的面积，如果当前面积大于area,那么修改area的值，反之则不变。
  2. 移动指向的对象值更小的指针。
if(height[left] < height[right]){
  left++;
}else{
  right++;
}
  1. 将结果area返回。

代码

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) return 0;
        int area = 0;
        int left = 0;
        int right = height.length-1;
        while (left < right){
            int currArea = (right-left)*Math.min(height[left], height[right]);
            if (currArea > area) area = currArea;
            if (height[left] < height[right]){
               left++;
            }else{
               right--;
            }
        }
        return area;
    }
}

2) 3Sum（Leetcode 15)

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

avatar

这道题的意思是输入一个无序数组，选出其中的三个值加起来等于0，找到所有不重复的这类可能性，并将它们以List的形式输出。

这道题目因为是计算三个数相加的值是否等于0，所以我们需要用到3个指针，不过我们可以将一个指针作为base指针，让它按顺序依次遍历整个数组，其它两个指针作为快慢指针来遍历base指针右侧的子数组。当然，由于这个数组为无序数组，我们需要先将其进行排序。

在base指针每一次向右移动后，我们需要重新初始化左右两个指针，然后计算三个指针所指值相加的和，和分为三种情况：

  1. 如果和等于0，就将三个值写入List并存在结果里，并移动两个指针。
  2. 如果和大于0，移动右指针。（因为数组被排序，移动右指针会使和变小）
  3. 如果和小于0，移动左指针。

Note: 这里要注意的是，一个数组中可能会有重复的值，为了避免出现重复结果，我们在移动所有指针时都需要跳过重复值，比如一个指针目前指的值为1时，下一次移动它时，要避开后面所有的值为1的index，从而跳转到下一个含有不同值的对象上。

解题步骤如下：

  1. 定义结果List result, 对数组进行排序。
List<List<Integer>> result = new LinkedList<>();
Arrays.sort(nums);
  1. 初始化base指针为数组最左端，开启while循环，当base < nums.length-2时停止循环，在循环的开头初始化left和right指针。
while(base < nums.length - 2){
  int right = nums.length - 1;
  int left = base + 1;
  ...
}
  1. 开启一个新的while循环，当左右指针相撞时停止循环。
while(left < right){
  	...
}
  1. 定义sum变量储存和的值，当和等于0时，将指针所指的值储存到result中并将左右指针都移动；当sum大于0时，只移动右指针；当sum小于0时，只移动左指针。
                if (sum == 0) {
                    result.add(Arrays.asList(nums[base], nums[left], nums[right]));
                    left = moveRight(nums, left + 1);
                    right = moveLeft(nums, right - 1);
                } else if (sum > 0) {
                    right = moveLeft(nums, right - 1);
                } else {
                    left = moveRight(nums, left + 1);
                }
  1. 当第二个循环结束后，将base指针向右移动一位。
base = moveRight(nums, base + 1);
  1. 实现moveLeft和moveRight函数。

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if (nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        int base = 0;
        while (base < nums.length - 2) {
            int right = nums.length - 1;
            int left = base + 1;
            while (left < right) {
                int sum = nums[base] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[base], nums[left], nums[right]));
                    left = moveRight(nums, left + 1);
                    right = moveLeft(nums, right - 1);
                } else if (sum > 0) {
                    right = moveLeft(nums, right - 1);
                } else {
                    left = moveRight(nums, left + 1);
                }
            }
            base = moveRight(nums, base + 1);
        }
        return result;
    }

    private int moveLeft(int[] nums, int right) {
        while (right == nums.length - 1 || (right >= 0 && nums[right] == nums[right + 1])) {
            right--;
        }
        return right;
    }

    private int moveRight(int[] nums, int left) {
        while (left == 0 || (left < nums.length && nums[left] == nums[left-1])){
            left++;
        }
        return left;
    }
}

IV. 总结

本文主要介绍了双指针算法中的左右对撞指针算法。此算法设立两个指针，从集合的两头向中心进行遍历，当指针相撞时停止。左右对撞指针算法在有序数组中使用非常普遍，所以遇到这类集合应当首先考虑使用左右对撞指针算法来求解。