1.3 关于双指针的一些总结
这篇内容主要是针对双指针的一些总结，方法比较巧妙，主要核心原理就是：有一个快指针fast、一个慢指针slow，slow指针主要作用就是存储真正的数组（也就是处理之后的结果），fast是辅助寻找元素，然后往slow里面放。
典型例题：
描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。（注意：需要返回的是int值，也就是需要返回数组长度）
示例：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
代码解决如下：
class Solution { public int removeElement(int[] nums, int val) { int slow = 0; for(int fast = 0;fast < nums.length;fast ++){ if(nums[fast]!=val){ nums[slow] = nums[fast]; slow++; } } return slow; } }
这个题目它的要求就是不创建新的数组，就在原数组上进行改动，这个是十分重要的。
删除有序数组中的重复元素
26. 删除有序数组中的重复项 - 力扣（LeetCode）
题目描述：
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
输入示例：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
解决代码：
class Solution { public int removeDuplicates(int[] nums) { int slow = 1; if(nums.length == 0) return 0; else if(nums.length == 1)return 1; for(int fast = 1;fast<nums.length;fast++){ if(nums[fast]!=nums[fast - 1]){ nums[slow] = nums[fast]; slow++; } } return slow; } }
这里注意的是，slow仍然是存放最终数组的，fast是辅助查询。
删除重复元素时，第一个元素肯定不重复，所以slow定为1。
fast判断的条件是比较是不是和前一个一样，只要不一样就放进去（这个需要保证顺利的前提才行）。
然后就是注意判断边界，数组长度为0的时候，不定义边界会溢出。
比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
这个题目采用的是StringBuffer栈来进行的，因为String是不可变的（虽然可以通过拼接的办法来改变，但那个是产生一个新的对象，同时也很麻烦）。
原理是，因为需要对比两个字符串，同时还是对这两个字符串做一样的操作，所以创建一个函数来进行操作是最好的。
题解如下：
class Solution { public boolean backspaceCompare(String s, String t) { return compareStr(s).equals(compareStr(t)); } public String compareStr(String s){ StringBuffer sb = new StringBuffer(); for(int i = 0;i < s.length();i ++){ char ch = s.charAt(i); if(ch != '#'){ sb.append(ch); } else{ if(sb.length()>0){ sb.deleteCharAt(sb.length() - 1); } } } return sb.toString(); } }
这里有许多之前没有使用过的对象和方法，首先就是StringBuffer类，它的创建方法和String类似，主要有这几种：
- StringBuffer s=new StringBuffer(); //创建一个空的StringBuffer类的对象。
- StringBuffer s=new StringBuffer(“abc”); //用一个已存在的字符串常量来创建StringBuffer类对象。
public static boolean backspaceCompare(String s, String t) { int len_s = s.length() - 1; int len_t = t.length() - 1; while (len_s >= 0 || len_t >= 0) { int skip_s = 0, skip_t = 0; while (len_s >= 0) { if (s.charAt(len_s) == '#') { skip_s++; len_s--; } else if (skip_s > 0) { skip_s--; len_s--; } else { break; } } while (len_t >= 0) { if (t.charAt(len_t) == '#') { skip_t++; len_t--; } else if (skip_t > 0) { skip_t--; len_t--; } else { break; } } if (len_s >= 0 && len_t >= 0 && s.charAt(len_s) != t.charAt(len_t)) { return false; } if ((len_s >= 0) != (len_t >= 0)) { return false; } len_s--; len_t--; } return true; }