26. 删除有序数组中的重复项
题目描述
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过： 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。
来源：力扣（LeetCode） 原题链接
问题分析
这个问题可以用一个简单的双指针解决。首先定义fast、slow指针，slow指向数组第一个元素，fast指向数组第二个元素。接下来fast指针在for循环中遍历数组。当fast指针指向的数与slow指针不相同时，slow指针便向右移动一位，此时slow指针指向的值被更新为fast指针所指向的值。但倘若fast与slow指向相同的数时，slow指针便不动，fast指针继续遍历直到遍历到不同的数。在遇到第一个不同的数之后，执行先前的操作：slow指针向后移动一位，其指向的值变为fast指针所指向的不同的数。一直这样下去，直到fast指针将数组遍历完。此时数组的有效长度为slow + 1，因为fast的初始值是1，遍历次数只有nums.size() - 1次。当数组的长度为0或1时，直接返回它本身的长度即可。
代码实现
283. 移动零
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
来源：力扣（LeetCode） 原题链接
问题分析 / 实现思路
初始化i，j指针，i指针为快指针，从头到尾遍历数组中的所有元素。快指针在遍历过程中，如果遇到的数不为0，那么慢指针随其一同向右移一位；如果遇到了0，快指针继续遍历但慢指针将留在原地。也就是说，我们用快指针遍历到的所有非零数都通过慢指针赋予给数组元素。遍历到最后，j的值便是非零元素的个数，数组的前j项便是其去除了所有0项的结果。此时我们将数组后面剩下的元素都赋值为0即可。
代码实现
844. 比较含退格的字符串
题目描述
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。 注意：如果对空文本输入退格字符，文本继续为空。 来源：力扣（LeetCode） 原题链接
使用栈的解法
由于栈的先进后出性质，用栈解本题十分方便。我们只需从前往后遍历，在遍历到的字符不为"#"时令其入栈，遇到"#"时令栈最上端的元素出栈，最后判断两个栈是否相等即可。但由于使用了栈，占用了额外空间，所以空间复杂度为O(n)。 注：此处并不一定要用c++的栈，可以使用字符串来模拟栈。因为最终两者比较时字符串更加方便。另外，由于#号可能在栈空的情况下出现，我们必须判断，并在栈非空的情况下pop_back。
双指针解法
本题可用快慢指针解决。《代码随想录》提供了另外一种双指针的解法——但理解上可能稍有困难，在文末会附上相关链接。快慢指针的思路是，将fast和slow指针指向数组的首端，fast开始遍历数组。当fast指针指向的元素不为#时，便更新slow指针所指向的值，并将slow指针右移一位；fast指针指向#时，slow指针便向左移动一位，指向的元素便是需要退格的元素。这里注意，因为#在索引为0的情况下是不需要操作的，所以需要判断条件else if (slow != 0)。
关于为什么slow指针此时指向的元素为需要被退格的元素：例如，数组总共有8个元素，在数组索引为3处有退格符。那么索引等于2的元素需要被退格。我们的快慢指针从索引0开始遍历，在遇到#前慢指针都是跟着快指针走。但当快指针指向#，也就是索引为3时，慢指针从3回退到2，循环继续。在下一个循环中，由于快指针右移，指向了索引为4的元素，慢指针指向的值便被更新为了该元素。也就是说，处于慢指针与快指针中间的元素此时均被忽略，索引为4的元素替代了索引为2的元素。以此类推，而在最后结束时，我们可以将数组resize为慢指针的大小，也就是此时数组的有效长度。
以下是《代码随想录》中提供的解法：
当然还可以有使用 O(1) 的空间复杂度来解决该问题。
同时从后向前遍历S和T（i初始为S末尾，j初始为T末尾），记录#的数量，模拟消除的操作，如果#用完了，就开始比较S[i]和S[j]。
如果S[i]和S[j]不相同返回false，如果有一个指针（i或者j）先走到的字符串头部位置，也返回false。
代码如下：
class Solution { public: bool backspaceCompare(string S, string T) { int sSkipNum = 0; // 记录S的#数量 int tSkipNum = 0; // 记录T的#数量 int i = S.size() - 1; int j = T.size() - 1; while (1) { while (i >= 0) { // 从后向前，消除S的# if (S[i] == '#') sSkipNum++; else { if (sSkipNum > 0) sSkipNum--; else break; } i--; } while (j >= 0) { // 从后向前，消除T的# if (T[j] == '#') tSkipNum++; else { if (tSkipNum > 0) tSkipNum--; else break; } j--; } // 后半部分#消除完了，接下来比较S[i] != T[j] if (i < 0 || j < 0) break; // S 或者T 遍历到头了 if (S[i] != T[j]) return false; i--;j--; } // 说明S和T同时遍历完毕 if (i == -1 && j == -1) return true; return false; } };
时间复杂度：O(n + m)
空间复杂度：O(1)
977. 有序数组的平方
题目描述
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
来源：力扣（LeetCode） 原题链接
排序解法
一般的思路是将该数组全部取绝对值然后排序并平方。不过由于排序的时间复杂度平均为O(nlogn)，不符合题目要求的O(n) ，故应用双指针解决。
双指针解法
上文解法忽略了题目所给的条件——原数组nums已按照升序排列。利用好这一点将大大优化时间复杂度。由于原数组中含有正负数，也就是说，平方后最大的数在数组的左右两端，越往数组中间靠近，那么该数平方后的值就越小。利用这个性质，我们可以定义左右指针，一个指向数组最左端，一个指向数组最右端。每次循环时，我们比较左指针与右指针所指向的数字的平方，将较大的那个数放在res（答案数组）的最左端（这一点比较好实现，因为答案数组与nums是等长的）。当该指针指向的数的平方被放入答案数组后，我们就能将该指针右移（左移）一位，在下一次循环中继续比较。在循环执行n次后，我们便得到了一个排好序的res数组，时间复杂度为O(n)。
