Array是最基础也是最常见的数据结构，String也可以看做是一个char array。通常我们需要通过index来访问array中的元素，所以要处理array的题目自然少不了index pointers，以下介绍array题目中最常用的双指针方法，可以用于解决一系列常见的array题目。

双指针Two Pointers

双指针是一种通过使用两个index pointers操作数据的方法，使用双指针来迭代数组的话，一个array会被分成3个区域：[0,i),[i,j],[j,array.len)。使用双指针时，我们必须要清楚地定义号每一区域的含义，才能后续的解题。双指针解法一般分为两种：同向和反向。

同向双指针

在同向双指针套路中，两个指针朝相同方向移动，但是快慢不同。其3个区域会被分割为下图所示：

同向双指针

其中[0,i)的数据代表处理好的数据，[i,j)中的数据是那些处理过但不需要的数据，[j,array.len)区间的数据为接下来待处理的数据。这里的3个区间的开合闭需要根据题目要求定义，但是要保持一致。用次方法处理过的数据，处理好的数据的相对位置要保持一致。同向双指针的解题步骤如下：

1. 初始化两个指针i和j，一般初始值为0
2. 当 while j<array.len:
   • 如果需要array[j],那通过，使array[i]=array[j],保留值，并使i往前进下一步
   • 否则跳过它，我们不需要移动 i 因为它的位置不符合条件。

反向双指针

反向双指针中的两个指针反向而行，同样分为3个区间

反向双指针

其中[0,i)和(j,array.len)内的数据均为处理好的数据，[i,j]中的数据待处理。用次方法处理过的数组不会保留原来元素的相对位置。解题步骤如下：

1. 初始化两个指针，i=0, j=array.len-1
2. while i<=j
   • 根据 array[i] 和 array[j] 的值决定你应该做什么
   • 向前移动至少一个指针

实践应用

接下来我们讲解两道经典题目，深入理解如何使用双指针解法

LeetCode344：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

public class LeetCode344 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        char[] s = {'h', 'e', 'l', 'l', 'o'};
        for (char i : s) {
            System.out.print(i);
        }
        solution.reverseString(s);
        System.out.print("\n******\n");
        for (char i : s) {
            System.out.print(i);
        }
    }

    static class Solution {
        public void reverseString(char[] s) {
            int left = 0, right = s.length - 1;
            while (left < right) {
                char tmp = s[left];
                s[left++] = s[right];
                s[right--] = tmp;
            }
        }
    }
}

LeetCode26:给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

public class LeetCode26 {
    public static void main(String[] args) {
        int[] nums1 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println("长度：" + removeDuplicates(nums1));
        int[] nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println("长度：" + removeDuplicates2(nums2));
        System.out.println(Arrays.toString(nums1));
        System.out.println(Arrays.toString(nums2));
    }

    //while 循环 同向双指针
    public static int removeDuplicates(int[] nums) {
        //异常处理
        if (nums == null || nums.length == 0) return 0;
        //初始化i 和j
        int i = 0, j = 1;
        while (j < nums.length) {
            //如果没有重复，保留，否则忽略
            if (nums[i] != nums[j]) {
                nums[i + 1] = nums[j];
                i++;
            }
            j++;
        }
        return i + 1;
    }

    // for 循环 同向双指针
    public static int removeDuplicates2(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
}

总结

可见双指针用来解决很多常见数组题目，其中包括同向和反向两个变种，大家根据题目的要求对3个区间做相对应的调整。以下是和双指针相关的经典题目。
LeetCode题目：11,42,283,80,1047