代码随想录day 01 二分法与快慢指针

发布时间 2023-12-27 11:54:05作者: 又见鸣蜩

二分法题目:

实现代码如下:

值得注意的是实现的方法是利用左闭右开区间还是左闭右闭区间
根据选择的不同,判断条件不同
将迭代的值带入到条件看符不符合区间要求就不会混淆二者

快慢指针题目:

本题实际上可以通过二重for循环暴力求解,复杂度是O(n^2)
但是测试过程中发现超时遂放弃

利用快慢指针在数组进行原地操作可以实现O(n)的时间复杂度

代码如下:

重点在于理解fast指向的是新数组所需的元素,slow指向的是新数组的下标
因而实际上fast只需要遍历一遍数组 然后slow在非目标值停顿一次
这样slow在遍历完成之后正好就是新数组的长度

实现过程漏掉了slow在fast赋值之后需要+1的操作 需要小心