算法Day07-算法研习指导之双指针

待我称王封你为后i 2022-11-29 12:47 166阅读 0赞

### 双指针技巧 ###

*  基本概念
 *  快慢指针
 *   *   *  判断链表中是否包含环
         *  返回有环链表中环的起始位置
         *  寻找链表的中点
         *  寻找链表的倒数第k个元素
 *  左右指针
 *   *   *  二分查找
         *  两数之和
         *  反转数组
         *  滑动窗口

# 基本概念 #

*  **双指针技巧分为两类:**
    
     *  **快慢指针:**
        
         *  主要解决**链表**中的问题
         *  比如判定链表中是否包含环
     *  **左右指针:**
        
         *  主要解决**数组**或者**字符串**问题
         *  比如二分查找

# 快慢指针 #

*  **快指针:**
    
     *  初始化指向链表的头结点**head**
     *  前进时快指针**fast**在前,慢指针**slow**在后
     *  可以巧妙解决链表中相关的问题

### 判断链表中是否包含环 ###

*  **单链表特点:**
    
     *  每个节点只知道下一个节点
     *  所以一个指针是无法判断链表中是否包含环的
 *  如果链表中不包含环,那么这个指针最终会遇到空指针**null.** 表示这个链表已经到头了,表示这个链表不包含环

boolean hasCycle(ListNode head) { 
    	while (head != null) { 
    		head = head.next();
    	}
    	return false;
    }

*  如果链表中含有环,那么这个指针就会陷入死循环. 因为环形数组中没有**null**指针作为尾部节点
 *  **使用双指针的快慢指针算法:**
    
     *  一个快指针**fast,** 一个慢指针**slow**
     *  如果不含有环,跑得快的指针快指针**fast**最终会遇到**null,** 说明链表中不含有环
     *  如果含有环,快指针**fast**最终会超过慢指针**slow**一圈,最终和慢指针**slow**相遇,说明链表中含有环

boolean haCycle(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;
    }

### 返回有环链表中环的起始位置 ###

ListNode detectCycle(ListNode head) { 
    	ListNode fast, slow;
    	fast = slow = head;
    	
    	while (fast != null && fast.next != null) { 
    		fast = fast.next.next;
    		slow = slow.next;
    			
    		if (fast == slow) { 
    			break;
    		}
    	}
    	slow = head;
    	while (slow != fast) { 
    		fast = fast.next;
    		slow = slow.next;
    	}
    	return slow;
    }

*  当快慢指针相遇时,让其中的任意指针指向头结点**head.** 然后快慢指针以相同的速度前进,再次相遇时所在的节点位置就是环的开始位置:
    
     *  第一次相遇时,如果慢指针**slow**走了**k**步,那么快指针**fast**一定走了**2k**步,即比慢指针**slow**多走了**k**步,也就是环长度的倍数
     *  假设相遇点距环的起点的距离为**m,** 那么环的起点距离头结点**head**的距离为**k-m,** 也就是说如果从头结点**head**前进**k-m**步就能到达环的起点
     *  如果从相遇点继续前**k-m**步,也恰好到达环起点
     *  因此,只要将快慢指针中的任意一个指针重新指向**head,** 然后两个指针以相同的速度前进,那么相遇之处就是环的起点

### 寻找链表的中点 ###

*  可以让快指针一次前进两步,慢指针一次前进一步,当快指针到达链表的尽头时,慢指针就处于链表中间的位置

while (fast.next != null && fast.next.next != null) { 
    	fast = fast.next.next;
    	slow = slow.next;
    }
    return slow;

*  当链表的长度为奇数时 **,slow**恰巧停在中点位置.如果长度为偶数 **,slow**最终的位置是中间位置偏右
 *  **寻找链表中点的作用:** 对链表进行归并排序
 *  **归并排序的重点就在于二分:**
    
     *  求中点,然后递归地将数组进行二分
     *  最后合并两个有序数组
     *  对于链表而言,合并两个有序链表的难点就在于二分

### 寻找链表的倒数第k个元素 ###

*  可以让快指针**fast**先走**k**步,然后快慢指针开始以相同的速度前进.这样当快指针**fast**走到链表的末尾**null**时,慢指针**slow**所在的位置就是倒数第**k**个链表节点,即慢指针**slow**所在位置的元素就是链表的倒数第k个元素

ListNode slow, fast;
    slow = fast = head;
    while (k --> 0) { 
    	fast = fast.next;
    }
    while (fast != null) { 
    	fast = fast.next;
    	slow = slow.next;
    }
    return slow;

# 左右指针 #

*  左右指针在数组中实际是指两个索引值
 *  初始化**left = 0, right = nums.length - 1**

### 二分查找 ###

int BinarySearch(int[] nums, int target) { 
    	int left = 0;
    	int right = nums.length - 1;
    	
    	while (left <= right) { 
    		int mid = left + (right - left)/2;
    		if (nums[mid] == target) { 
    			return mid;
    		} else if (nums[mid] < target) { 
    			left = mid + 1;
    		} else if (nums[mid] > target) { 
    			right = mid - 1;
    		}
    	}
    	return -1;
    }

### 两数之和 ###

*  只要数组有序,就应该使用双指针技巧
 *  通过调节**left**和**right**可以调整**sum**的大小

int twoSum(int[] nums, int target) { 
    	int left = 0, right = nums.length - 1;
    	while (left < right) { 
    		int sum = nums[left] + nums[right];
    		if (sum == target) { 
    			return new int[] { left + 1, right + 1};
    		} else if (sum < target) { 
    			left++;
    		} else if (sum > target) { 
    			right--;
    		}
    	}
    	return new int[] { -1, -1};
    }

### 反转数组 ###

void reverse(int[] nums) { 
    	int left = 0;
    	int right = nums.length - 1;
    
    	while (left < right) { 
    		// 转换数组左指针和右指针的元素
    		int temp = nums[left];
    		nums[left] = nums[right];
    		nums[right] = temp;
    		left++;
    		right--;
    	}
    }

### 滑动窗口 ###

*  使用双指针的滑动窗口算法,可以解决字符串匹配问题
 *  一般遇到字符串匹配问题以及子串相关问题,首先想到使用滑动窗口算法