27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
Solution: 使用快慢指针， 快指针遍历数组，当找到不等于target的数组元素时，用该元素覆盖慢指针位置，随后慢指针+1. 最后慢指针指向新数组末尾位置，返回作为新数组长度即可。
class Solution {
public int removeElement(int[] nums, int val) {
int fastIdx = 0, slowIdx = 0;
while (fastIdx < nums.length) {
if (nums[fastIdx] != val) {
nums[slowIdx++] = nums[fastIdx];
}
++fastIdx;
}
return slowIdx;
}
}
26. 删除排序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
Solution: 与 27. 移除元素 基本相同，注意由于要保留一个重复元素，故慢指针先+1，然后再用快指针指向值覆盖慢指针位置。由于慢指针最后指向新数组最后一个元素，最后返回慢指针+1作为长度。
class Solution {
public int removeDuplicates(int[] nums) {
int fastIdx = 0, slowIdx = 0;
for (; fastIdx < nums.length; ++fastIdx) {
if (nums[fastIdx] != nums[slowIdx]) {
nums[++slowIdx] = nums[fastIdx];
}
}
return slowIdx + 1;
}
}
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
Solution: 等同快慢指针，但是需要把慢指针之后的位置全部补0。
class Solution {
public void moveZeroes(int[] nums) {
int fastIdx = 0, slowIdx = 0;
for (; fastIdx < nums.length; ++fastIdx) {
if (nums[fastIdx] != 0) {
nums[slowIdx++] = nums[fastIdx];
}
}
for (; slowIdx < nums.length; ++slowIdx) {
nums[slowIdx] = 0;
}
}
}
844. 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意： 如果对空文本输入退格字符，文本继续为空。
Solution: 本题采用s和t分别双指针，由于退格只影响前面的字符，故从后往前遍历，一个指针idx表示索引，一个指针skip表示需要退格的字符数。遇到#时，skip增加1，遇到普通字符时，如果skip大于0，那么当前字符需要忽略，skip减去1；否则说明当前字符不需要忽略。使用两个同层while循环来分别找到s和t（从后往前）第一个不需要忽略的字符，进行比较，如果不相等即可判定s和t不等；如果有一个字符串的已经遍历完成而另一个没有，也可以判定不等；否则继续寻找。
class Solution {
public boolean backspaceCompare(String s, String t) {
int s_idx = s.length() - 1, t_idx = t.length() - 1;
int s_skip = 0, t_skip = 0;
while (s_idx >= 0 || t_idx >= 0) {
while (s_idx >= 0) {
if (s.charAt(s_idx) == '#') ++s_skip;
else if (s_skip > 0) --s_skip;
else break;
--s_idx;
}
while (t_idx >= 0) {
if (t.charAt(t_idx) == '#') ++t_skip;
else if (t_skip > 0) --t_skip;
else break;
--t_idx;
}
if (s_idx == -1 && t_idx == -1) return true;
else if (s_idx >= 0 && t_idx >= 0) {
if (s.charAt(s_idx) != t.charAt(t_idx)) return false;
}
else return false;
--s_idx;
--t_idx;
}
return true;
}
}
977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
Solution: 这题同样使用双指针，左指针指向原数组开头，右指针指向数组末尾。由于结果数组中最大的平方数其原数一定在原数组两端，以此类推，使用两个指针从原数组两端往中间逼近，将（左指针和右指针指向元素中）更大的那个平方数从后往前填入结果数组，然后对应指针往中间移动1，直到左指针>右指针为止。
class Solution {
public int[] sortedSquares(int[] nums) {
int leftIdx = 0, rightIdx = nums.length - 1, resultIdx = rightIdx;
int[] result = new int[nums.length];
int leftSquare, rightSquare;
while (leftIdx <= rightIdx) {
leftSquare = nums[leftIdx] * nums[leftIdx];
rightSquare = nums[rightIdx] * nums[rightIdx];
if (leftSquare >= rightSquare) {
result[resultIdx--] = leftSquare;
++leftIdx;
} else {
result[resultIdx--] = rightSquare;
--rightIdx;
}
}
return result;
}
}