【快慢指针法】
考虑:谁设循环,边界是什么,步长是什么,移动条件是什么
:谁走得快谁设循环---->快指针,边界是数组长度(不溢出),步长为1,移动条件以数组[0,1,2,3,3,0,4,2]为例,当快指针所指向的元素与val不符,那我们期望数组不做改变,指针继续往前走,当快指针所指元素等于val值,则希望当前指针后续的所有元素都往前移动。此时,如果考虑当nums[fast]==val作为条件对数组进行改动的话,比如当fast=2,nums[fast]val2,让low指针指向当前位置,fast不断后移把元素往前搬,这就会退化成双重循环的暴力解法,与我们想要的效果不符,所以需要考虑另一种条件:当快指针所指元素与val不符时,数组做出改变
这样循环会有两种情况出现:
①nums[fast]==val
此时此刻low指针会与fast指针同在,因为没遇到val,low指针不语只是一味地跟随,那么当遇到了val,fast指针需要找到下一个不是val的元素把当前val覆盖掉,也就只需要fast循环,当出现!=val的情况,则会覆盖掉
②nums[fast]!=val
我们希望数组不发生改变,也就是元素不移动,那么可以原地交换,nums[low++]=nums[fast],慢指针仅仅跟随快指针
int removeElement(int* nums, int numsSize, int val) {//快慢指针int low=0;for(int fast=0;fast<numsSize;fast++){if(nums[fast]!=val){nums[low++]=nums[fast];}}return low;
}