双指针算法原理,双指针算法是什么

《算法通关村——双指针妙用》 删除元素 描述

给你一个数组 nums 和一个值 val你需要原地移除所有数值等于 val 的元素并返回移除后数组的新长度。要求不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

例子1: 输入nums  [3,2,2,3], val  3 输出2, nums  [2,2] 例子2 输入nums  [0,1,2,2,3,0,4,2], val  2 输出5, nums  [0,1,4,0,3]

三种解决方法解决

/** * 删除指定元素用快慢指针,慢指针用于填充不删除的值快指针用于查找目标值 * param nums * param val * return */public static  int removeElement(int[] nums,int val){    int slow  0;    // fast充当快指针    for(int fast  0;fast<nums.length;fast){        if(nums[fast] ! val){            nums[slow]  nums[fast];            slow;        }    }    return slow;}/** * 对撞指针的方法两个指针从两边走左边如果不相等不等于目标值就往后right等于目标值就往前。 * param nums * param val * return */public static int removeElement1(int[] nums,int val){    int right  nums.length-1;    int left  0;    while(left < right){        if((nums[left]val) && (nums[right]! val)){            int temp  nums[right];            nums[right]  nums[left];            nums[left]  temp;        }        if(nums[left] ! val)  left;        if(nums[right]val) right--;    }    return left;}/** * 双指针覆盖这种就是直接覆盖了如果从左开始有值等于目标值就把他替换成从右边开始的值然后右边指针移动左边不动 * 然后再次判断左边原位置是否是目标值如果是就继续覆盖右边指针继续移动如果不是左边指针移动。 * param nums * param val * return */public static int removeElement2(int[] nums, int val){    int right  nums.length - 1;    for(int left  0; left<right;){        if(nums[left]  val){            nums[left]  nums[right];            right--;        }else{            left;        }    }    return right1;}

删除重复项 描述

给你一个有序数组 nums 请你原地删除重复出现的元素使每个元素只出现一次 返回删除后数组的新长度。不要使用额外的数组空间你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例1 输入nums  [1,1,2] 输出2, nums  [1,2] 解释函数应该返回新的长度 2 并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。  例子2 输入nums  [0,0,1,1,1,2,2,3,3,4] 输出5, nums  [0,1,2,3,4] 解释函数应该返回新的长度 5  并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

解决

/** * 删除数组中重复元素返回数组的大小。慢指针进行存值覆盖快指针判断是否为重复值。 * param nums * return */public static int removeDuplicates(int[] nums){    // slow表示可以放入新元素位置索引为0的元素不用管.    int slow  1;    // 循环起到了快指针的作用    for(int fast  0;fast < nums.length;fast){        if(nums[fast] ! nums[slow-1]){            nums[slow]  nums[fast];            slow;        }    }    return slow;}

近期在自学 Java 做项目加入了一个编程学习圈子里面有编程学习路线和原创的项目教程感觉非常不错。还可以 1 对 1 和大厂嘉宾交流答疑也希望能对大家有帮助扫 ⬇️ 二维码即可加入。

也可以点击链接我正在「编程导航」和朋友们讨论有趣的话题你⼀起来吧