算法通关村——第三关

双指针思想及其应用

双指针思想

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

删除元素

原地移除所有数值等于 val 的元素
第一种：快慢双指针
定义两个指针slow和fast，初始值都是0。
Slow之前的位置都是有效部分，fast表示当前要访问的元素。
这样遍历的时候，fast不断向后移动：

• 如果nums[fast]的值不为val，则将其移动到nums[slow++]处。
• 如果nums[fast]的值为val，则fast继续向前移动，slow先等待。
  

public static int removeElement(int[] nums, int val) {
 int slow = 0;
 //fast充当了快指针的角色
 for (int fast = 0; fast < nums.length; fast++) {
	 if (nums[fast] != val) {
		 nums[slow] = nums[fast];
		 slow++;
	 }
 }
 //最后剩余元素的数量
	 return slow;
}

第二种：对撞双指针
核心思想是从右侧找到不是val的值来顶替左侧是val的值。

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 ;
}

为什么循环里要用left<=right。如果没有的话是否可以，left==right的时候必须要再执行一次循环，让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;
}

现快慢型双指针留下的元素顺序与原始序列中的是一致的，而在对撞型中
元素的顺序和原来的可能不一样了。