【LeetCode】双指针：同向快慢针

前言今日练习目的掌握两个指针通向遍历同一序列的解法快针通常用于寻找目标慢针用于记录写入位置283:移动零题目要求给定一个数组讲数组中为0的元素放在数组最后同时保持非0元素的相对顺序核心思路定义一个快指针快速遍历数组所有元素一个慢指针指向下一个非0元素应该存放的位置具体流程fast从头扫描到尾遇到非零元素将其放在slow位置slow最后slow之后的元素全部为0代码实现intslow0;for(intfast0;fastnums.length;fast){if(nums[fast]!0){inttempnums[fast];nums[fast]nums[slow];nums[slow]temp;slow;}}总结要有快慢指针思想同一个数组中寻找元素进阶写法减少时间复杂度把非0往前放同时把0自动丢到后面27移动元素题目要求给你一个数组nums和一个值val要求原地删除所有等于val的元素返回删除后数组的新长度核心思路与上一题类似代码实现classSolution{publicintremoveElement(int[]nums,intval){intslow0;intnnums.length;for(intfast0;fastn;fast){if(nums[fast]!val){inttempnums[fast];nums[fast]nums[slow];nums[slow]temp;slow;}}returnslow;}}总结与上一题同样的思路直接return slowslow即为新数组长度26删除有序数组中的重复项题目要求一个非严格递增排列的数组 nums要求原地删除重复元素并返回新数组长度核心思考对于原地删除重复元素我们要想到用后续不重复元素去覆盖前一个重复元素。代码实现classSolution{publicintremoveDuplicates(int[]nums){intslow0;for(intfast1;fastnums.length;fast){if(nums[fast]!nums[slow]){slow;nums[slow]nums[fast];}}returnslow1;}}本题进阶如果题目给的数组元素顺序是完全无序的我们应该想到HashSet来去重代码实现HashSetIntegersetnewHashSet();intslow0;for(intfast0;fastnums.length;fast){if(!set.contains(nums[fast]){set.add(nums[fast]);nums[slow]nums[fast];slow;}}returnslow;总结情况方法有序数组双指针无序数组HashSet无序 不允许额外空间排序 双指针19删除链表的倒数第N个节点题目要求给定一个链表head和一个整数n要求删除倒数第n个节点返回删除后的链表头核心思路其实思路还是一样只不过本题换成了链表代表了以下几个地方有修改需要先创建一个虚拟头节点让fast/slow与链表接轨链表的遍历方式不一样走一步为fastfast.next删除节点slow.next slow.next.next;直接改变指针定位返回值dummy.next、代码实现classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummynewListNode(0);dummy.nexthead;ListNodefastdummy;ListNodeslowdummy;// fast先走n步for(inti0;in;i){fastfast.next;}// 一起走while(fast.next!null){fastfast.next;slowslow.next;}// 删除节点slow.nextslow.next.next;returndummy.next;}}总结掌握链表的语法详见核心思路