leetcode｜数组；二分；快慢指针

type

status

date

slug

summary

首先，在面对数组时，我们必须清楚，数组中的元素在内存中是连续分布的，单独删除一个元素是不可实现的，所以当出现类似删除原数组元素之类的要求时（也可理解为在原数组上进行元素个数变化的操作），操作应为覆盖元素，这是十分基础的知识。

下面以题目来具体分析快慢指针与二分，以及笔者在刷题时遇到的一些idea

另外附上评论区看到的做法

咋看一眼感觉很高大上，但其实就是快慢指针思想，只不过slow变成了j，fast变成了i，if的内容变成了原先else的，fast初始值从1开始，结束时把原数组最后一个也包含在内；这样省去了最后的赋值，稍微精简一些。这其实是良好运用了自增自减运算符，配合初值，结束条件等共同造成的。

leetcode27题也是用一样的思想即可解决，当然笔者最开始想到的并非快慢指针，但也并非carl写的暴力解法（双层for循环）

细看便可知，笔者开辟了一个常量数组的空间来方便改变。

844题，也是用快慢指针，那个退格符可对应为负责赋值的slow减一；值得注意的是，题目注意说对空文本输入#还应该是空文本，说明空文本时（代码即slow=0）若遇到#，slow不变（保持为0）

最后讲一下二分，首先要明白，二分的使用条件是有序数组，无重复元素

其次，二分涉及区间，大致可分为[left,right];[left,right)这两种区间，相对应的，while循环中的条件就有<=和<的区别，right,left后期赋值多少也是要

考虑到元素到底有没有涉及到。（注意，第二种区间right初值为数组大小）

总结：用快慢指针对数组进行覆盖元素操作能避免多重循环，且仅在原数组上操作，占用空间少；

二分不难，关键要细致；

要注意到程序的细节，比如if判断语句是否可能出现触及不该触及的内存等，以及循环结束条件，循环不变量等等；

防溢出问题（此篇中用数学方法解决，之前遇到自建int变量溢出，改为了long）

对特殊情况的处理讨论（首先确定其是否真的特殊）。