双指针算法
双指针包括快慢指针和左右指针。快慢指针一般用来对链表进行操作，比如判断链表是否有环、寻找中间结点或者倒数某个结点等等；而左右指针一般是对数组进行操作，比如二分查找、滑动窗口等等。
Ⅰ 快慢指针
1、判断链表是否有环（LeetCode 141）
经典解法就是用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。
//快指针速度是慢指针速度的两倍
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
//快慢指针首先都在头节点
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
//快慢指针先移动再判断
fast = fast.next.next;
slow = slow.next;
if (slow == fast) return true;
}
return false;
}
}
思考：快指针的速度可以是慢指针速度的三倍？
答：可以。只是判断条件都得加上fast.next.nex ?= null，导致更加繁琐。
//快指针速度是慢指针速度的三倍
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null || head.next.next == null)
return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null && fast.next.next != null) {
fast = fast.next.next.next;
slow = slow.next;
if (slow == fast) return true;
}
return false;
}
}
2、已知链表有环，求环的起始节点（LeetCode 142）
第一次相遇时，假设慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步，fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。
image-20201214131504079
设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。不用管 fast 在环里到底转了几圈，反正走 k 步可以到相遇点，那走 k - m 步一定就是走到环起点了。所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后就会相遇，相遇之处就是环的起点了。
shaunzhizhen2
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) { //找到交点了
return findStart(head,fast);
}
}
return null;
}
//将快指针重新放到头节点head，跟慢结点以相同速度走，相遇处即为环的起点
ListNode findStart (ListNode head,ListNode meetNode) {
ListNode fast = head;
ListNode slow = meetNode;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
3、寻找链表中点（LeetCode 876）
当链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏右。寻找链表中点的一个重要作用是对链表进行归并排序。
class Solution {
public ListNode middleNode(ListNode head) {
if (head.next == null) return head;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
4、寻找链表的倒数第N个元素（LeetCode 19）
先让快指针走n步，走完后要判断要删除的是不是头节点！！
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = head;
for (int i=0;i<n;i++) {
fast = fast.next;
}
if (fast == null) { //删除的是头节点
return head.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
}
Ⅱ 左右指针（只总结滑动窗口，解决无序子串问题，有序子串要考虑动态规划）
基本框架
关键：need和window两个HashMap，left和right左右两个指针，以及valid匹配上的元素个数
/* 滑动窗口算法框架 */
//s为给定字符串，t为待匹配的子串
void slidingWindow(string s, string t) {
//need记录待查找字符串各个字符的数量，window是记录滑动窗口内含待查找字符的数量
HashMap<Character, Integer> need, window;
for (char c : t) need.put(key, map.getOrDefault(key, 0) + 1);
int left = 0, right = 0; //左右指针
//valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size() 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 t。
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
System.out.println("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 进行窗口内数据的一系列更新
...
// 左移窗口
left++;
}
// 右移窗口
right++;
}
}
1、最小覆盖字串（LeetCode 76）
需要引入start和end记录最小的子串。注意Integer.intvalue()是把Integer转化为int，而Integer.valueOf()把int转化为Integer。
自动装箱都是通过包装类的valueOf()方法来实现的；自动拆箱都是通过包装类对象的xxxValue()来实现的。
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer> need = new HashMap<>();
for (int i=0;i<t.length();i++) {
char ch = t.charAt(i);
need.put(ch,need.getOrDefault(ch,0).intValue()+1);
}
Map<Character,Integer> window = new HashMap<>();
int left = 0;int right = 0;
int valid = 0;
//用来记录最小的子串
int start = 0;int end = Integer.MAX_VALUE;
while (right < s.length()) { //滑动右窗口
char ch1 = s.charAt(right);
//如果need里面包含这个字符
if (need.containsKey(ch1)) {
window.put(ch1,window.getOrDefault(ch1,0).intValue()+1);
//某一个字符在window里面的个数与need里面相等了，即该元素满足了要求
if (window.get(ch1).intValue() == need.get(ch1).intValue()) {
valid++;
}
//开始对左侧窗口进行滑动。注意是while不是if！！
while (valid == need.size()) {
//判断是否是长度最小的字符串
if (right-left < end-start) {
start = left;
end = right;
}
char ch2 = s.charAt(left);
//开始滑动窗口左侧
if (window.containsKey(ch2)) {
window.put(ch2,window.get(ch2).intValue()-1);
//如果ch2的个数在window里面不足了，对应的valid需要--。
if (window.get(ch2).intValue() < need.get(ch2).intValue()) {
valid--;
//至此一个周期的窗口滑动结束，右窗口准备右滑进行下一个滑动周期
}
}
left++;
}
}
//need不包含直接right++
right++;
}
return end == Integer.MAX_VALUE ? "" : s.substring(start,end+1);
}
}
2、字符串的排列（LeetCode 567）
给定两个字符串 s1 和s2，写一个函数来判断 s2是否包含s1的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。本题与上一题不同的是，字串中间不能夹杂别的字母，总体过程基本一样。
示例:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
class Solution {
//注意看请s1和s2代表啥，不要弄反了
public boolean checkInclusion(String s1, String s2) {
Map<Character,Integer> need = new HashMap<>();
for (int i=0;i<s1.length();i++) {
char ch = s1.charAt(i);
need.put(ch,need.getOrDefault(ch,0).intValue()+1);
}
Map<Character,Integer> window = new HashMap<>();
int left = 0,right = 0,valid = 0;
while (right < s2.length()) {
char ch1 = s2.charAt(right);
if (need.containsKey(ch1)) {
window.put(ch1,window.getOrDefault(ch1,0).intValue()+1);
if (window.get(ch1).intValue() == need.get(ch1).intValue()) {
valid++;
}
//准备开始滑动左侧窗口
while (valid == need.size()) {
if (right-left+1 == s1.length()) {
return true;
}
char ch2 = s2.charAt(left);
if (window.containsKey(ch2)) {
window.put(ch2,window.get(ch2).intValue()-1);
if (window.get(ch2).intValue() < need.get(ch2).intValue()) {
valid--;
}
}
left++;
}
}
right++;
}
return false;
}
}
3、找到字符串的所有字母易位词（LeetCode 438）
image-20201214200415345
与上一题字符串的排列基本上一样，只是找到一个满足的结果时不要返回，还要继续找
class Solution {
public List<Integer> findAnagrams(String s, String p) {
Map<Character,Integer> need = new HashMap<>();
for (int i=0;i<p.length();i++) {
char ch = p.charAt(i);
need.put(ch,need.getOrDefault(ch,0).intValue()+1);
}
Map<Character,Integer> window = new HashMap<>();
int left = 0,right = 0,valid = 0;
List<Integer> res = new ArrayList<>();
while (right < s.length()) {
char ch1 = s.charAt(right);
if (need.containsKey(ch1)) {
window.put(ch1,window.getOrDefault(ch1,0).intValue()+1);
if (window.get(ch1).intValue() == need.get(ch1).intValue()) {
valid++;
}
while (valid == need.size()) {
if (right-left+1 == p.length()) {
res.add(left);
}
char ch2 = s.charAt(left);
if (need.containsKey(ch2)) {
window.put(ch2,window.getOrDefault(ch2,0).intValue()-1);
if (window.get(ch2).intValue() < need.get(ch2).intValue()) {
valid--;
}
}
left++;
}
}
right++;
}
return res;
}
}
4、无重复字符的最小子串（LeetCode 3）
与前几题相比，不需要need这个计数器。
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
Map<Character,Integer> window = new HashMap<>();
int left = 0,right = 0,valid = 0;
int len = 0;
while (right < s.length()) {
char ch = s.charAt(right);
window.put(ch,window.getOrDefault(ch,0).intValue()+1);
while (window.get(ch) > 1) { //开始去重
char ch2 = s.charAt(left);
window.put(ch2,window.get(ch2).intValue()-1);
left++;
}
//去重之后再计算长度
len = Math.max(len,right-left+1);
right++;
}
return len;
}
}
Ⅲ 其他双指针题目
1、最长回文子串（LeetCode 5）
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) return s;
String res = s.substring(0,1);
int maxLen = 1;
for (int i=0;i<len;i++) {
//子串为奇数的情况
String oddStr = helper(s,i,i);
//子串为偶数的情况
String evenStr = helper(s,i,i+1);
String tmp = oddStr.length() > evenStr.length()?oddStr:evenStr;
if (tmp.length() > maxLen) {
maxLen = tmp.length();
res = tmp;
}
}
return res;
}
//求字符串s在left到right区间的最长字串
String helper (String s,int left ,int right) {
while (left>=0 && right<s.length()) {
if (s.charAt(left) == s.charAt(right)) {
left--;right++;
}else break;
}
return s.substring(left+1,right);
}
}
