您好！
欢迎来到京东云开发者社区
登录
首页
博文
课程
大赛
工具
用户中心
开源
首页
博文
课程
大赛
工具
开源
更多
用户中心
开发者社区
>
博文
>
数据结构与算法之双指针
分享
打开微信扫码分享
点击前往QQ分享
点击前往微博分享
点击复制链接
数据结构与算法之双指针
自猿其说Tech
2021-08-24
IP归属：未知
28120浏览
计算机编程
今天来通过5个力扣题来分享下数据结构与算法中的一个解题方法——双指针，目录大纲如下。  ### 1 删除有序数组中的重复项 力扣地址：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/   举个例子，大概就是想这样，最后返回4，因为有4个不同的数字  ```java class Solution { public int removeDuplicates(int[] nums) { // 当数组为0时，返回0 if(nums.length==0){ return 0; } // 定义慢指针 int last = 0; // 定义快指针 int fast = 0; // 当快指针没有走到末尾的时候 while(fast<nums.length){ // 如果慢快指针指向的数值不等于慢指针指向的数值 if(nums[fast] != nums[last]){ // 慢指针向前移动一位 last++; // 将慢指针指向的数值变成快指针指向的数值 nums[last] = nums[fast]; } //快指针向前移动一位 fast++; } // 返回满指针+1 这个时候就是不重复数组的长度 return last+1; } } ``` 这其中最主要的就是 ```java // 当快指针没有走到末尾的时候 while(fast<nums.length){ // 如果慢快指针指向的数值不等于慢指针指向的数值 if(nums[fast] != nums[last]){ // 慢指针向前移动一位 last++; // 将慢指针指向的数值变成快指针指向的数值 nums[last] = nums[fast]; } //快指针向前移动一位 fast++; } ``` - 慢指针和快指针都是是从左边第一个元素开始走的 - 慢指针确保的是，从左边第一个元素到满指针指向的元素，这些元素不重复 当快指针没有走到末尾的时候，快指针无论如何都要向前走。 - 当快指针指向的数值与慢指针指向的相等的时候，这个时候就意着，数据开始重复，而我们慢指针确保的是不重复数据，那么，慢指针不动，让快指针继续向前走 - 当快指针指向的数值与慢指针指向的不等的时候，这个时候就意着慢指针需要向前移动，慢指针向前移动一位后，需要把此时慢指针指向的数值变成刚才那个快指针指向的数值，因为我们慢指针确保的是从最左边开始是不重复数据   ### 2 移除元素 力扣地址：https://leetcode-cn.com/problems/remove-element/   举个例子，大概是这样  ```java class Solution { public int removeElement(int[] nums, int val) { if(nums.length == 0){ return 0; } int slow =0; int fast =0; // 快指针不到末尾时 while(fast<nums.length){ //快指针不等于需要移除的数值时 if(nums[fast] != val){ //将快指针指向的数值赋值给慢指针 nums[slow] = nums[fast]; //慢指针继续前移 slow ++; } //快指针移动 fast++; } return slow; } } ``` - 慢指针指向的数都是最终数组中的，是删除要删除的数据后的数组 - 当我们快指针指向要删除的数据的时候，慢指针不动，快指针前移 - 当我们快指针指向的不是要删除的数据的时候，将快指针指向的数值赋值给慢指针，然后慢指针向前移动一位，快指针前移   ### 3 长度最小的子数组 力扣地址：https://leetcode-cn.com/problems/minimum-size-subarray-sum/  ```java class Solution { public int minSubArrayLen(int target, int[] nums) { if(nums.length == 0){ return 0; } // 窗口左边界 int left = 0; // 窗口右边界 int right = 0; //总和 int sum =0; // 默认滑动窗口长度 int result = Integer.MAX_VALUE; // 当滑动窗口右边界没到末尾的时候 while(right <nums.length ){ // 计算滑动窗口内的总和 sum = sum + nums[right]; // 当这次的总和 >= 目标值 while(sum >=target){ // 更新滑动窗口的长度，用上次长度和这次的滑窗长度比，取最短的 result = Math.min(result, right- left+1); // 更新总和，减去左边界的值 sum = sum - nums[left]; // 滑动窗口左边界向右移动，收缩滑动窗口 left++; } // 滑动窗口右边界向右移动 right++; } // 如果result没变的话，代表没有符合条件的子数组，返回0，否则返回result return result == Integer.MAX_VALUE ? 0: result; } } ``` 流程如下，主要观察图中绿色的滑动窗口的变化    ### 4 最大连续1的个数 II 力扣地址：https://leetcode-cn.com/problems/max-consecutive-ones-ii/  ```java class Solution { public int findMaxConsecutiveOnes(int[] nums) { int left = 0; int right = 0; // 0的个数 最大为1 int zeroCount = 0; int result =0; while(right <nums.length){ if(nums[right] == 0){ zeroCount++; } // 0的个数大于一时 while(zeroCount>1){ // 当左指针指向的数值是0的时候，0的个数减一 if(nums[left] == 0){ zeroCount--; } // 移动左指针 left++; } // 更新结果 result = Math.max(result, right-left+1); //右指针移动 right++; } return result; } } ``` 流程如下，主要观察图中绿色的滑动窗口的变化   ### 5 最大连续1的个数 III 力扣地址：https://leetcode-cn.com/problems/max-consecutive-ones-iii/  这个题和上个题的唯一区别就是由一开始允许的1个0变成了K个0 代码变化也不大，就是由1变成了K,完整代码如下 ```java class Solution { public int longestOnes(int[] nums, int k) { int left =0; int right =0; int zeroCount =0; int result =0; while(right<nums.length){ if(nums[right] == 0){ zeroCount++; } while(zeroCount >k){ if(nums[left] ==0){ zeroCount--; } left++; } result = Math.max(result, right - left +1); right++; } return result; } } ``` ### 6 总结 双指针，就是定义两个指针在指定的数组/链表上游走，在做一些自定义的操作。 如果要细分的话，双指针有左右指针，快慢指针，滑动窗口三种类型，一般时间复杂度为O(n)，空间复杂度为O(1),这就是双指针的精妙之处 ------------ ###### 自猿其说Tech-JDL京东物流技术发展部 ###### 作者：中台技术部 邢焕杰
原创文章，需联系作者，授权转载
上一篇：垃圾回收器-ZGC的设计思路
下一篇：一起学习Collections.sort()中的Timsort
相关文章
Taro小程序跨端开发入门实战
Flutter For Web实践
配运基础数据缓存瘦身实践
自猿其说Tech
文章数
426
阅读量
2149964
作者其他文章
01
深入JDK中的Optional
本文将从Optional所解决的问题开始，逐层解剖，由浅入深，文中会出现Optioanl方法之间的对比，实践，误用情况分析，优缺点等。与大家一起，对这项Java8中的新特性，进行理解和深入。
01
Taro小程序跨端开发入门实战
为了让小程序开发更简单，更高效，我们采用 Taro 作为首选框架，我们将使用 Taro 的实践经验整理了出来，主要内容围绕着什么是 Taro，为什么用 Taro，以及 Taro 如何使用（正确使用的姿势），还有 Taro 背后的一些设计思想来进行展开，让大家能够对 Taro 有个完整的认识。
01
Flutter For Web实践
Flutter For Web 已经发布一年多时间，它的发布意味着我们可以真正地使用一套代码、一套资源部署整个大前端系统（包括：iOS、Android、Web）。渠道研发组经过一段时间的探索，使用Flutter For Web技术开发了移动端可视化编程平台—Flutter乐高，在这里希望和大家分享下使用Flutter For Web实践过程和踩坑实践
01
配运基础数据缓存瘦身实践
在基础数据的常规能力当中，数据的存取是最基础也是最重要的能力，为了整体提高数据的读取能力，缓存技术在基础数据的场景中得到了广泛的使用，下面会重点展示一下配运组近期针对数据缓存做的瘦身实践。
自猿其说Tech
文章数
426
阅读量
2149964
作者其他文章
01
深入JDK中的Optional
01
Taro小程序跨端开发入门实战
01
Flutter For Web实践
01
配运基础数据缓存瘦身实践
添加企业微信
获取1V1专业服务
扫码关注
京东云开发者公众号
28120浏览
