数组题目中有两种双指针的应用：和快慢指针 。 目录如下：
双指针（左右）
双指针（快慢）
相关题目有：
344，反转字符串
26，删除排序数组中的重复项
27，移除元素
283，移动零
485，最大连续1的个数
540，有序数组中的单一元素
209，长度最小的子数组
双指针（左右）
左右指针在数组中实际是指两个索引值，一般初始化为left = 0, right = nums.length - 1。循环条件为 while(left < right) 。
在上篇文章二分查找 中，凸出了双指针特性。在下面题目中体会。
看到题目要求有【原地修改】的要求，一般都采用双指针。
167，两数之和Ⅱ，easy
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
题解
只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节left和right可以调整sum的大小
代码
class Solution public int [] twoSum(int [] numbers, int target) { int n = numbers.length; int left = 0 ; int right = n - 1 ; while (left < right){ if (numbers[left] + numbers[right] == target) return new int []{left + 1 , right + 1 }; else if (numbers[left] + numbers[right] < target) left++; else right--; } return new int []{0 ,0 }; } }
344，反转字符串，easy
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]
代码
class Solution public void reverseString (char [] s) if (s == null ) return ; int left = 0 ; int right = s.length - 1 ; while (left < right){ char temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; } } }
双指针（快慢）
快慢指针在数组中实际是指两个索引值，快指针始终在慢指针的前面，一般初始化为 slow = 0, fast = 0 或 1。循环条件为 while(fast < nums.length) 。
框架
public int f&s(int [] nums) { if (nums.length == 0 || nums == null ) return 0 ; int slow = 0 ; int fast = 0 或 1 ; while (fast < nums.length){ if (nums[fast] != ...){ ... slow = ... } fast++; } return ...; }
26，删除排序数组中的重复项，easy
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度 。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
题解
快慢指针初始指向索引0和1，用快指针探路，慢指针保存没有重复元素的数组。
快指针向前，直到不和 当前慢指针指向元素 重复，慢指针索引+1，指向元素为新的数字。
动画演示
代码
class Solution public int removeDuplicates (int [] nums) if (nums.length == 0 ) return 0 ; int slow = 0 ; int fast = 1 ; while (fast < nums.length){ if (nums[slow] != nums[fast]){ slow++; nums[slow] = nums[fast]; } fast++; } return slow + 1 ; } }
注： 类似题目：83.删除排序链表中的重复元素
27，移除元素，easy
你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度 。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。 注意这五个元素可为任意顺序。
题解
快慢指针初始都指向首个元素，快指针用于探路，如果不等于 val，则可以进行覆盖；如果等于 val，继续向前。
代码
class Solution public int removeElement (int [] nums, int val) if (nums.length == 0 || nums == null ) return 0 ; int slow = 0 ; int fast = 0 ; while (fast < nums.length){ if (nums[fast] != val){ nums[slow] = nums[fast]; slow++; } fast++; } return slow; } }
细节
上一题要求是删除重复元素，fast 移到下一个不重复元素时，索引slow++，并将fast 指向的值赋给 nums[slow]，最后得到数组长度为 索引数slow + 1。
这里是先给nums[slow]赋值然后再给slow++，这样可以保证nums[0..slow-1]是不包含值为val的元素的，最后的结果数组长度就是slow。
283，移动零，easy
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。
题解
与上一题类似，只是删除操作改成了移动操作。
代码
class Solution public void moveZeroes (int [] nums) if (nums.length == 0 || nums == null ) return ; int slow = 0 ; int fast = 0 ; while (fast < nums.length){ if (nums[fast] != 0 ){ int temp = nums[fast]; nums[fast] = nums[slow]; nums[slow] = temp; slow++; } fast++; } } }
另一种解法
遍历此数组，如果当前元素不为0，就赋给慢指针所在位置的元素，遍历结束再将慢指针之后的元素赋为 0。可以看成建立了新的数组，但是是在原数组上改变的。
class Solution public void moveZeroes (int [] nums) if (nums.length == 0 ) return ; int index = 0 ; for (int i = 0 ; i < nums.length; i++){ if (nums[i] != 0 ) nums[index++] = nums[i]; } for (int i = index; i < nums.length; i++){ nums[i] = 0 ; } } }
485，最大连续1的个数，easy
给定一个二进制数组， 计算其中最大连续1的个数。
示例 1:
输入: [1,1,0,1,1,1] 输出: 3 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
注意：
输入的数组只包含 0 和1。
输入数组的长度是正整数，且不超过 10,000。
题解
快慢指针初始都指向首个元素，快指针移至最后一个非 0 元素，fast - slow 即为当前连续1 的个数。当 nums[fast] = 0 时，slow 移至 fast 之后再开始统计。重复上述步骤直至 fast 遍历到最后一个元素。
代码
class Solution public int findMaxConsecutiveOnes (int [] nums) if (nums.length == 0 || nums == null ) return 0 ; int slow = 0 ; int fast = 0 ; int res = 0 ; while (fast < nums.length){ if (nums[fast] != 1 ){ res = Math.max(res, fast - slow); slow = fast + 1 ; } fast++; } return Math.max(res, fast - slow); } }
细节
注意考虑数组全为 1 的情况，返回值为 fast - slow 。
另一种解法
一次遍历。两个计数器 count、maxCount作为计数指针 和 当前连续1 的最大个数。
class Solution public int findMaxConsecutiveOnes (int [] nums) if (nums.length == 0 || nums == null ) return 0 ; int count = 0 ; int maxCount = 0 ; for (int i = 0 ; i < nums.length; i++){ if (nums[i] != 0 ){ count++; maxCount = Math.max(count, maxCount); }else { count = 0 ; } } return maxCount; } }
下面两题稍有不同，但总体思想大致一致。
540，有序数组中的单一元素，medium
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8] 输出: 2
示例 2:
输入: [3,3,7,7,10,11,11] 输出: 10
代码：
class Solution public int singleNonDuplicate (int [] nums) int slow = 0 ; int fast = 1 ; while (fast < nums.length){ if (nums[slow] < nums[fast]) return nums[slow]; if (nums[slow] == nums[fast]){ slow = slow + 2 ; fast = fast + 2 ; } } return nums[slow]; } }
209，长度最小的子数组，medium
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
题解
快慢指针来维护一个滑动窗口，相当于数组元素入队出队。具体过程可以用队列来理解，但代码实现用快慢指针。
代码
class Solution public int minSubArrayLen (int s, int [] nums) int slow = 0 ; int fast = 0 ; int sum = 0 ; int min = Integer.MAX_VALUE; while (fast < nums.length){ sum += nums[fast]; fast++; while (sum >= s){ min = Math.min(min, fast - slow); sum -= nums[slow]; slow++; } } return min == Integer.MAX_VALUE ? 0 : min; } }
