双指针算法
转载自:双指针算法基本原理和实践
什么是双指针?
双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。
换言之,双指针法充分 使用了数组有序这一特征,从而在某些情况下能够简化一些运算。
对撞指针
对撞指针是指在数组中,将指向最左侧的索引定义为左指针(left),最右侧的定义为右指针(right),然后从两头向中间进行数组遍历。
对撞数组适用于 连续数组 和字符串,也就是说当你遇到题目给定连续数组和字符床时,应该第一时间想到用对撞指针解题
伪代码大致如下:
public void find (int[] list) {
var left = 0;
var right = list.length - 1;
//遍历数组
while (left <= right) {
left++;
// 一些条件判断 和处理
... ...
right--;
}
}
反转字符串
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[]
的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1:
输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]
示例 2:
输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]
解答 可以套用前面的伪代码:
class Solution {
public void reverseString(char[] s) {
if (s.length == 0 || s.length == 1) return ;
int left = 0;
int right = s.length-1;
while (left <right) {
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
return ;
}
}
长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足 其和 ≥ s 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例:
输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
解答:
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int right = 0;
int left = 0;
int sum = 0;
int len = Integer.MAX_VALUE; // 用于标识这个 len 是否改变过
while(right < nums.length) {
sum += nums[right];
while (sum >= s) {
// 这里的 right - left + 1 实际上就是窗口大小
len = Math.min(right - left + 1, len);
sum -= nums[left];
left++;
}
right++;
}
// len = Integer.MAX_VALUE 表示 len 没有变过
if (len == Integer.MAX_VALUE) return 0;
return len;
}
}
虽然这道题目也是用的双指针,但是实际上采用滑动窗口的算法思想
快慢指针
快慢指针也是双指针,但是两个指针从同一侧开始遍历数组,将这两个指针分别定义为快指针(fast)和慢指针(slow),两个指针以不同的策略移动,例如 fast 每次增长两个,slow 每次增长一个,直到两个指针的值相等(或其他特殊条件)为止。
快慢指针一般都初始化指向链表的头结点 head,前进时快指针 fast 在前,慢指针 slow 在后,巧妙解决一些链表中的问题。
判定链表中是否含有环
单链表的特点是每个节点只知道下一个节点,所以一个指针的话无法判断链表中是否含有环的。
如果链表中不包含环,那么这个指针最终会遇到空指针 null 表示链表到头了,这还好说,可以判断该链表不含环。
boolean hasCycle(ListNode head) {
while (head != null)
head = head.next;
return false;
}
但是如果链表中含有环,那么这个指针就会陷入死循环,因为环形数组中没有 null 指针作为尾部节点。
经典解法就是用两个指针,一个每次前进两步,一个每次前进一步。如果不含有环,跑得快的那个指针最终会遇到 null,说明链表不含环;如果含有环,快指针最终会和慢指针相遇,说明链表含有环。
就好像一个环形跑道上有一快一慢两个运动员赛跑,如果时间足够长,跑地快的运动员一定会赶上慢的运动员。
boolean hasCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow)
return true;
}
return false;
}
链表中倒数第k个节点(中等)
题目描述: 输入一个链表,输出该链表中倒数第k个结点。 如果该链表长度小于k,请返回空。
示例1
{1,2,3,4,5},1
返回值
{5}
解题思路:快慢指针,先让一个指针指向头节点,先走 K 步,如果为空就返回空,反之,就再让一个指针从头节点出发,快慢指针一起走,直到快指针为空,输出慢指针
即:倒数的 + 顺数的长度等于链表总长度,所以当 fast 指针为 null 时,剩下的慢指针所在的地方就是目标了
如下图所示
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
if(pHead == null) return pHead;
ListNode fast = pHead;
int i = 0;
while(i < k){
if(fast == null) return fast;
fast = fast.next;
i++;
}
ListNode slow = pHead;
while(fast != null){
slow = slow.next;
fast = fast.next;
}
return slow;
}