部分图文参考于：代码随想录 - 移除元素和力扣官方解法。
1.题目1★：27.移除元素
1.1.解法1：暴力解法
考验对数组底层实现的理解：数组的元素是不能删的，只能覆盖。
通过两层for循环来求解，外层for循环遍历数组元素，内层for循环将目标值进行覆盖。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for(int i = 0; i < size; i++)
{
if(nums[i] == val)
{
for(int j = i + 1; j < size; j++)
{
nums[j - 1] = nums[j];
}
i--;
size--;
}
}
return size;
}
};
● 时间复杂度：\(O(n^2)\)
● 空间复杂度：\(O(1)\)
1.2.解法2：双指针法
1.双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
2.定义快慢指针:
● 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组。
● 慢指针：指向更新 新数组下标的位置。
例如下图，当val = 3时，fast指针到3处时，slow指针指向3，当fast指向4时，slow指针仍然指向3，并将”3“覆盖。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
for(int fast = 0; fast < nums.size(); fast++)
{
if(nums[fast] != val)
{
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
};
● 时间复杂度：\(O(n)\)
● 空间复杂度：\(O(1)\)
1.3.解法3：双指针法（优化）
这样的方法两个指针在最坏的情况下合起来只遍历了数组一次，避免了需要保留的元素的重复赋值操作。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0, right = nums.size();
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
};
● 时间复杂度：\(O(n)\)
● 空间复杂度：\(O(1)\)
2.题目2：26. 删除有序数组中的重复项
2.1.解法1：双指针法
慢指针：指向新数组元素需要更替的位置。
快指针：寻找不重复元素。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 1;
for (int fast = 1; fast < nums.size(); fast++) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
};
● 时间复杂度：O(n)
● 空间复杂度：O(1)
3.题目3：283. 移动零
3.1.解法1：双指针法
快指针：寻找不为0的元素。
慢指针：指向数组内需要更新的元素位置。
快指针始终向前寻找，当快指针寻找到不为0的元素时，便与慢指针所在位置元素进行交换，慢指针继续前进。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
}
}
};
● 时间复杂度：O(n)。
● 空间复杂度：O(1)。
4.题目4★：844. 比较含退格的字符串
4.1.解法1：重构字符串（栈）
最容易想到的方法是将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。然后直接比较两字符串是否相等即可。
具体地，我们用栈处理遍历过程，每次我们遍历到一个字符：
● 如果它是退格符，那么我们将栈顶弹出；
● 如果它是普通字符，那么我们将其压入栈中。
class Solution {
public:
string build(string s) { // 重新构造字符串
string st;
for (auto c : s) {
if (c != '#') { // 检测到非'#'时，元素入栈
st.push_back(c);
}
else if (!st.empty()) { // 检测到'#'时，弹出元素。这里注意对栈空的判断，栈空时，不弹出元素。
st.pop_back();
}
}
return st;
}
bool backspaceCompare(string s, string t) {
return build(s) == build(t);
}
};
● 时间复杂度：O(n+m)，其中n和m分别为字符串s和t的长度。我们需要遍历两字符串各一次。
● 空间复杂度：O(n+m)，其中n和m分别为字符串s和t的长度。主要为还原出的字符串的开销。
4.2.解法2：双指针法
1.双指针在这里用于处理字符串，快指针寻找'#'，如果元素是'#'，慢指针回退（相当于删除字符），否则更新当前位置的元素。最终慢指针所指的位置等于字符串处理后的最终长度。
2.分别求出字符串s和字符串t的最终长度sLen和tLen，如果不相等则返回false，再依次对比单个字符串是否相等。
class Solution {
public:
bool backspaceCompare(string s, string t) {
int sLen = deal(s);
int tLen = deal(t);
if (sLen != tLen) return false; // 如果s和t最终字符串的长度不一样，返回false
for (int i = 0; i < sLen; i++) { // 遍历比较剩下的字符是否对应相等
if (s[i] != t[i]) return false;
}
return true;
}
private:
// 双指针法
int deal(string &str) {
int slow = 0;
for (int fast = 0; fast < str.size(); fast++) {
if (str[fast] == '#') { // 快指针找到#后
if (slow != 0)
slow--; // 慢指针回退，相当于删除元素
}
else str[slow++] = str[fast]; // 否则更新元素，慢指针前进
}
return slow; // 返回的是删除字符后字符串的长度
}
};
● 时间复杂度：O(n+m)。其中n和m分别为字符串s和t的长度。我们需要遍历两字符串各一次。
● 空间复杂度：O(1)。对于每个字符串，我们只需要定义一个指针和一个计数器即可。