双指针思想及其应用

一、双指针思想

 这里介绍一种简单但非常有效的方式一双指针。所谓的双指针其实就是两个变量，不一定真的是指针。双指针思想简单好用，在处理数组、字符串等场景下很常见。
 看个例子，从下面序列中删除重复元素[1,2,2,2,3,3,3,5,5,7,8],重复元素只保留一个。删除之后的结果应该为[1,2,3,5,7,8]。我们可以在删除第一个2时将将其后面的元素整体向前移动一次，删除第二个2时再将其后的元素整体向前移动一次，处理后面的3和5都一样的情况，这就导致我们需要执行5次大量移动才能完成，效率太低。
 如果使用双指针可以方便的解决这个问题，如图：

 首先我们定义两个指针slow、fast。slow表示当前位置之前的元素都是不重复的，而fast则一直向后找，直到找到与slow位置不一样的，找到之后就将slow向后移动一个位置，并将arr[fast]复制给arr[slow],之后fast继续向后找，循环执行。找完之后slow以及之前的元素就都是单一的了。这样就可以只用一轮移动解决问题。
 上面这种一个在前一个在后的方式也称为快慢指针，有些场景需要从两端向中间走，这种就称为对撞型指针或者相向指针，很多题目也会用到，我们接下来会看到很多相关的算法题。
还有一种比较少见的背向型，就是从中间向两边走。这三种类型其实非常简单，看的只是两个指针是一起向前走，还是从两头向中间走，还是从中间向两头走。

二、删除元素专题

原地移除所有数值等于val的元素

 LeetCode27.给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。要求：不要使用额外的数组空间，你必须仅使用O(1)额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

 在删除的时候，从删除位置开始的所有元素都要向前移动，所以这题的关键是如果有很多值为val的元素的时候，如何避免反复向前移动呢？
本题可以使用双指针方式，而且还有三种，我们都看一下：

第一种：快慢双指针

 整体思想就是一开始介绍的双指针的图示的方式，定义两个指针slow和fast,初始值都是0。Slow之前的位置都是有效部分，fast表示当前要访问的元素。
这样遍历的时候，fast不断向后移动：
1.如果nums[fast]的值不为val,则将其移动到nums[slow]处，然后slow向前移动。
2.如果nums[fast]的值为val,则fast继续向前移动，slow先等待。

这样做，数组的前半部分是有效部分，后半部分是无效部分

class Solution {public int removeElement(int[] nums, int val) {if(nums.length == 0) return 0;int slow = 0,fast = 0;for(fast = 0; fast < nums.length; fast++){if(nums[fast] != val){nums[slow] = nums[fast];slow++;}}return slow;}
}

第二种：对撞双指针

 对撞指针，有的地方叫做交换移除，核心思想是从右侧找到不是val的值来顶替左侧是vl的值。以nums=[0,1,2,2,3,0,4,2],val=2为例：

 上图完整描述了执行的思路，当left==right的时候，Ieft以及左侧的就是删除掉2的所有元素了。实现代码：

public int removeElement(int[] nums,int val){int right = nums.length - 1;int left = 0;for (left = 0; left <= right;){if ((nums[left] == val) && (nums[right] != val)){int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;}if (nums[left] != val)left++;if (nums[right] == val)right--;}return left;
}

 这样就是一个中规中矩的的双指针解决方法。上面图中很多同学可能感觉为什么循环里要用Ieft<=right。如果没有的话是否可以，答案是不可以，我们看一个例子，如果序列是[3,2,2,3]，val=3:看执行图：

此时会发现，left==right的时候必须要再执行一次循环，让left再执行一次++才是正确结果。

第三种：对撞双指针+覆盖

 拓展本题还可以进一步融合上面两种方式创造出：“对撞双指针+覆盖”法。当nums[left]等于val的时候，我们就将nums[right]位置的元素覆盖nums[left],继续循环，如果nums[left]等于val就继续覆盖，否则才让left++,这也是双指针方法的方法，实现代码：

public int removeElement(int[]nums, int val){int right = nums.length-1;for (int left = 0;left <= right;){if (nums[left] == val){nums[left] = nums[right];right--;}else left++;}return right + 1;
}

删除有序数组中的重复项

 LeetCode26给你一个有序数组nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

 本题使用双指针最方便，思想与前面的一样，一个指针负责数组遍历，一个指向有效数组的最后一个位置。为了减少不必要的操作，我们做适当的调整，例如令slow=1,并且比较的对象换做nums[slow-1],
代码如下：

public static int removeDuplicates(int[] nums){//slow表示可以放入新元素的位置，索引为0的元素不用管int slow = 1;//循环起到了快指针的作用for (int fast = 0;fast < nums.length; fast++){if (nums[fast] != nums[slow - 1]){nums[slow] = nums[fast];slow++;}}return slow;
}

三、元素奇偶移动专题

 根据某些条件移动元素也是一类常见的题目，例如排序本身就是在移动元素，这里看一个奇偶移动的问题。
 LeetCode905,按奇偶排序数组。给定一个非负整数数组A,返回一个数组，在该数组中，A的所有偶数元素之后跟着所有奇数元素。你可以返回满足此条件的任何数组作为答案。

 最直接的方式是使用一个临时数组，第一遍查找并将所有的偶数复制到新数组的前部分，第二遍查找并复制所有的奇数到数组后部分。

class Solution {public int[] sortArrayByParity(int[] nums) {int n = nums.length;int[] res = new int[n];int left = 0, right = n - 1;for (int num : nums) {if (num % 2 == 0) {res[left++] = num;} else {res[right--] = num;}}return res;}
}

 这种方式实现比较简单，但是会面临面试官的灵魂之问："是否有空间复杂度为0(1)的"方法。我们可以采用对撞型双指针的方法，图示与2.5.2中的对撞型基本一致，只不过比较的对象是奇数还是偶数。如下图所示：

 维护两个指针left=0和right=arr.length-1,left从0开始逐个检查每个位置是否为偶数，如果是则跳过，如果是奇数则停下来。然后right从右向左检查，如果是奇数则跳过偶数则停下来。然后交换array[left]和array[right]。之后再继续巡循环，直到left>=right。

public static int[]sortArrayByParity(int[] A){int left = 0,right = A.length - 1;while (left < right){if (A[left] % 2 > A[right] % 2){int tmp = A[left];A[left] = A[right];A[right] = tmp;}if (A[left] % 2 == 0)left++;if (A[right] % 2 == 1)right--;}return A;
}

四、数组轮转问题

 先看题目要求，LeetCode189.给你一个数组，将数组中的元素向右轮转k个位置，其中k是非负数。

 这个题怎么做呢？你是否想到可以逐次移动来实现？理论上可以，但是实现的时候会发现要处理的情况非常多，比较难搞。这里介绍一种简单的方法：两轮翻转。
方法如下：
1.首先对整个数组实行翻转，例如[1,2,3,4,5,6,7]我们先将其整体翻转成[7,6,5,4,3,2,1]。
2.从k处分隔成左右两个部分，这里就是根据k将其分成两组[7,6,5]和[4,3,2,1]。
3.最后将两个再次翻转就得到[5,6,7]和[1,2,3,4]，最终结果就是[5,6,7,1,2,3,4]
这个方法非常巧妙，力扣里时间复杂度击败100%

class Solution {public void rotate(int[] nums, int k) {int split = k % nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, split - 1);reverse(nums, split, nums.length - 1);}public void reverse(int[] nums, int begin, int end){while(begin < end){int temp = nums[begin];nums[begin] = nums[end];nums[end]  = temp;begin++;end--;}}
}

 下面的代码是自己写的时候用的笨方法，利用类似前面旋转链表(力扣65)的方法，把数组截断成两部分，然后用新数组先装后面的部分，再装前面的部分

class Solution {public void rotate(int[] nums, int k) {int split = (nums.length - 1) - (k % nums.length);int[] newnums = new int[nums.length];int j = 0;for(int i = split + 1; i < nums.length; i++){newnums[j] = nums[i];j++;}for(int i = 0; i <= split; i++){newnums[j] = nums[i];j++;}int m = 0;for(int num : newnums){nums[m++] = num;}}
}

五、数组的区间专题

 数组中表示的数据可能是连续的，也可能是不连续的，如果将连续的空间标记成一个区间，那么我们可以再造几道题，先看一个例子：
 LeetCode228.给定一个无重复元素的有序整数数nums。返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于nums的数字×。列表中的每个区间范围[a,b]应该按如下格式输出：
“a->b”,如果a!=b;
“a”,如果a==b;

 本题容易让人眼高手低，一眼就看出来结果，但是编程实现则很麻烦。这个题使用双指针也可以非常方便的处理，慢指针指向每个区间的起始位置，快指针从慢指针位置开始向后遍历直到不满足连续递增（或快指针达到数组边界)，则当前区间结束；然后将slow指向更新为fst+1,作为下一个区间的开始位置，fast继续向后遍历找下一个区间的结束位置，如此循环，直到输入数组遍历完毕。

class Solution {public List<String> summaryRanges(int[] nums) {List<String> list = new ArrayList<>();int slow = 0, fast = 0;while(fast < nums.length){if(fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]){StringBuffer str = new StringBuffer();str.append(nums[slow]);if(slow != fast){str.append("->" + nums[fast]);}slow = fast + 1;list.add(str.toString());}fast++;   }return list;}
}

 这个实现的精华是"fast+1=nums.length‖nums[fast]+1!=nums[fast+1]",我们是用fast+1来进行比较的，如果使用fast比较也可以，但是实现起来会有些case一直过不了，不信你可以试一下。（数组会越界）

字符串替换空格问题

 这是剑指offer中的题目，出现频率也很高：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20 Happy。
 首先要考虑用什么来存储字符串，如果是长度不可变的char数组，那么必须新申请一个更大的空间。如果使用长度可变的空间来管始数组，或者原始数组申请得足够大，这时候就可能要求你不能申请O(n)大小的空间，我们一个个看。
 首先是如果长度不可变，我们必须新申请一个更大的空间，然后将原始数组中出现空格的位置直接替换成%20即可，代码如下：

public String replaceSpace(StringBuffer str){
String res = "";
for(int i=0; i<str.length(); i++){char c = str.charAt(i);if(c == ''） res += "%20";else res + c;
}
return res;
}

 对于第二种情况，我们首先想到的是从头到尾遍历整个字符串，遇到空格的时候就将其后面的元素向后移动2个位置，但是这样的问题在前面说过会导致后面的元素大量移动，时间复杂度为O(2),执行的时候非常容易超时。
 比较好的方式是可以先遍历一次字符串，这样可以统计出字符串中空格的总数，由此计算出替换之后字符串的长度，每替换一个空格，长度增加2，即替换之后的字符串长度为：
新串的长度=原来的长度+2*空格数目
 接下来从字符串的尾部开始复制和替换，用两个指针fst和slow分别指向原始字符串和新字符串的末尾，然后：slow不动，向前移动fast:
1.若指向的不是空格，则将其复制到slow位置，然后fast和slow同时向前一步；
2.若fast指向的是空格，则在slow位置插入一个%20，fast则只移动一步。
循环执行上面两步，便可以完成替换。详细过程如下：

代码实现如下

public String replaceSpace(StringBuffer str){
if（str == null) return null;
int numOfblank = 0;//空格数量
int len = str.length();
for(int i = 0; i < len; i++){//计算空格数量if(str.charAt(i) == ' ') numOfblank++;
}
str.setLength(len + 2 * numOfblank),//设置长度
int fast = len-1;//两个指针
int slow = (len + 2 * numOfblank) - 1;
while (fast >= 0 && slow > fast){char c = str.charAt(fast);if(c == ' '){fast--;str.setCharAt(slow--, '0');str.setCharAt(slow--, '2')str.setCharAt(slow--, '%')}else{str.setCharAt(slow,c);fast--;sLow--;}
}
return str.tostring();
}