欢迎关Android茶话会回pdf取阿里&字节经典面试题、Android、算法、Java等系列武功秘籍 在技能学习、个人成长的道路上，让咱们一同行进！
前语
双指针技巧在算法题中算是常用技巧了，让咱们省去for循环，降低杂乱度，一般双指针技巧能够分为2大类
- 快慢指针：首要处理链表中的问题，比方链表是否有环，删除倒数第N个节点等
- 左右指针：首要处理数组、字符串中的问题，比方二分查找、翻转数组等
下面将详细介绍下
快慢指针
下面结合实例来介绍快慢指针在实际中的用途
判别链表是否有环
单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判别链表中是否含有环的。假如链表中不含环，那么这个指针最终会遇到空指针 null 表明链表到头了，这还好说，能够判别该链表不含环，假如链表含有环，那么单独一个指针就会堕入死循环。 这时候双指针的效果就体现了，咱们运用2个指针，一个跑的快，一个跑的慢。假如没有环的话，跑得快的会遇到null，假如有环的话，快指针最终会和慢指针相遇
booleanhasCycle(ListNodehead){
ListNodefast,slow;
fast=slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow)returntrue;
}
returnfalse;
}
链表是否有环，有的话回来这个环的开端方位
- 先找相遇点 判别是否有环
- 有环的话重置其间一个指针到起点，相同速度行进，再次相遇便是节点方位开端的方位
publicListNodedetectCycle(ListNodehead){
ListNodeslow,fast;
slow=fast=head;
booleanhasRecycle=false;
//快慢指针找到交点
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast){
hasRecycle=true;
break;
}
}
if(!hasRecycle){
returnnull;
}
//将其间一个重置到起点,再一同移动，下次相交便是相遇点
slow=head;
//intindex=0;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
//index++;
if(slow==fast)break;
}
returnslow;
}
❝
解说下原理 能够看到，当快慢指针相遇时，让其间任一个指针指向头节点，然后让它俩以相同速度行进，再次相遇时所在的节点方位便是环开端的方位。这是为什么呢？
❞
第一次相遇时，假定慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步，也便是说比 slow 多走了 k 步（也便是环的长度) 假定慢指针回到环的起点，设相遇点距环的起点间隔为m，slow和fast再次相遇之后行走间隔为k，，那么距头结点head的间隔为k-m, 此刻快指针间隔相遇点也是k-m，因而慢指针回到节点之后两指针同速行进，k-m步就会相遇，相遇的地方便是环的起点了
寻找链表的倒数K个元素
让快指针先走 k 步，然后快慢指针开端同速行进。这样当快指针走到链表末尾 null 时，慢指针所在的方位便是倒数第 k 个链表节点（为了简化，假定 k 不会超越链表长度）
ListNodeslow,fast;
slow=fast=head;
while(k-->0)
fast=fast.next;
while(fast!=null){
slow=slow.next;
fast=fast.next;
}
returnslow;
移除元素
给你一个数组 nums 和一个值 val，你需求 原地 移除所有数值等于 val 的元素，并回来移除后数组的新长度
不要运用额定的数组空间，你必须仅运用 O(1) 额定空间并 原地 修正输入数组。
这儿咱们就能够运用快慢指针，在[0，slow)中的元素都是值不等于val=target的元素，fast指针用于扫描整个数组
publicintremoveElement(int[]nums,intval){
//慢指针slow区间[0,slow)内的元素为值不等于val的元素
intslow=0;
for(intfast=0;fast<nums.length;fast++){
//快指针fast所指向的元素值不等于val=3
//将其值赋值于慢指针所在方位
if(nums[fast]!=val){
nums[slow]=nums[fast];
//赋值完毕之后，慢指针右移一位，等候下一次赋值
slow++;
}
}
returnslow;
}
左右指针
左右指针一般是运用两头索引值，一般初始化为 left = 0, right = nums.length – 1
二分查找
二分查找是经典的左右指针，(需求留意的细节是开闭区间),本题运用闭区间 [0,nums.length-1]
intbinarySearch(int[]nums,inttarget){
intleft=0;
intright=nums.length-1;
if(nums[(left+right)/2]==target)return(left+right)/2;
while(left<=right){
intmid=(right+left)/2;
if(nums[mid]==target)
returnmid;
elseif(nums[mid]<target)
left=mid+1;
elseif(nums[mid]>target)
right=mid-1;
}
return-1;
}
反转字数组(字符串)
字符串也是同理
voidreverse(int[]nums){
intleft=0;
intright=nums.length-1;
while(left<right){
//swap(nums[left],nums[right])
inttemp=nums[left];
nums[left]=nums[right];
nums[right]=temp;
left++;right--;
}
}
两数之和
int[]twoSum(int[]nums,inttarget){
intleft=0,right=nums.length-1;
while(left<right){
intsum=nums[left]+nums[right];
if(sum==target){
//题目要求的索引是从1开端的
returnnewint[]{left+1,right+1};
}elseif(sum<target){
left++;//让sum大一点
}elseif(sum>target){
right--;//让sum小一点
}
}
returnnewint[]{-1,-1};
}
滑动窗口
略微杂乱一点的双指针运用，中心便是保护一个窗口，调整窗口的大小，重点把握的是
- 窗口内是什么
- 窗口开端方位怎么移动
- 窗口完毕方位怎么移动
伪代码如下
intleft=0,right=0;
while(right<s.size()){
//增大窗口
window.add(s[right]);
right++;
//窗口数据更新……
while(windowneedsshrink){
//缩小窗口
window.remove(s[left]);
left++;
}
}
image.png
看个经典算法题
❝
209.长度最小的子数组(mid)-滑动窗口 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 接连 子数组，并回来其长度。假如不存在符合条件的子数组，回来 0，如: 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解说：子数组 [4,3] 是该条件下的长度最小的子数组。
❞
//滑动窗口
funminSubArrayLen(target:Int,nums:IntArray):Int{
varsum=0
varsubLength=0
varresult=Int.MAX_VALUE
//滑动窗口开端方位
varleft=0
for(rightinnums.indices){
//开端累加
sum+=nums[right]
//滑动窗口
while(sum>=target){
subLength=right-left+1
result=if(result<subLength)resultelsesubLength
//移动窗口左边界
sum-=nums[left++]
}
}
returnif(result==Int.MAX_VALUE)0elseresult
}
关于滑动窗口 B站也有解说视频 www.bilibili.com/video/BV1V4…
欢迎关 Android茶话会 回 pdf 取阿里&字节经典面试题、Android、算法、Java等系列武功秘籍
在技能学习、个人成长的道路上，让咱们一同行进！
您的 点赞、评论，是对我的巨大鼓舞！
