算法打卡第二天/数组增删改查及双指针法

一，今日学习任务

第 2 天 数组增删改查及双指针法

今日任务： 27. 移除元素

题目建议： 暴力的解法，可以锻炼一下我们的代码实现能力，建议先把暴力写法写一遍。 双指针法 是本题的精髓，今日需要掌握，至于拓展题目可以先不看。

题目链接：https://leetcode.cn/problems/remove-element/
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

二，初次解题思路和思考

刚拿到这道题，第一反应就是最直白的暴力解法：
遍历数组，遇到等于目标值val的元素，就把它后面的所有元素往前挪一位，把这个值覆盖掉。
这种方法逻辑简单，写起来没难度，但时间复杂度太高了，最坏情况要把整个数组挪一遍，效率太差，肯定不是最优解。

再仔细想，题目要求原地修改数组，不能用额外空间，还得高效，那肯定就是用双指针法了。
双指针的核心就是用两个指针，一个快一个慢，一次遍历就把数组处理完，直接把时间复杂度从O(n²)降到O(n)，完美符合要求。

三，写代码时核心注意点

我最容易搞混的就是两个指针的作用和移动逻辑，总结了几个关键要点：

1. 两个指针到底干嘛用？

◦ 慢指针：指向「新数组」里，下一个要放元素的位置

◦ 快指针：遍历原数组，找「不需要移除」的元素

2. 什么时候移动指针？

◦ 快指针一直往后走，遍历整个数组

◦ 只有当快指针找到不等于val的元素时，才把这个元素赋值给慢指针的位置，然后慢指针往后挪一位

◦ 如果快指针遇到了val，直接跳过，慢指针不动

3. 暴力法的坑
暴力法里，元素前移之后，当前位置要重新检查，不然会漏过连续的val，这个细节很容易写错。

四，操作

测试示例

输入：
nums = [3,2,2,3]，val = 3
输出：2，新数组为[2,2]

输入：
nums = [0,1,2,2,3,0,4,2]，val = 2
输出：5，新数组为[0,1,3,0,4]

五，今天收获

1. 双指针法是数组原地修改的核心技巧，能大幅优化时间复杂度，必须吃透

2. 暴力法适合练手，但面试一定要用双指针，体现算法思维

3. 数组的元素移动会改变数组长度，处理时一定要注意索引的变化，避免越界

4. 遇到「原地修改数组」「移除元素」这类问题，第一反应就该想到双指针