题目+日期
- 移除元素 2023年5月14日17点50分
基础知识
暴力解法
这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
双指针法（快慢指针法）
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置
如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
相关题目
26.删除排序数组中的重复项✔
83.删除排序链表中的重复元素✔
283.移动零✔:即移除0，然后slow后元素赋值为零
844.比较含退格的字符串
方法一：重构字符串
977.有序数组的平方
拓展
滑动窗口算法
滑动窗口算法的快慢指针特性：
left 指针在后，right 指针在前，两个指针中间的部分就是「窗口」，算法通过扩大和缩小「窗口」来解决某些问题。
滑动窗口算法框架
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
char c = s[right];
// 右移（增大）窗口
right++;
// 进行窗口内数据的一系列更新
while (window needs shrink) {
char d = s[left];
// 左移（缩小）窗口
left++;
// 进行窗口内数据的一系列更新
}
}
}