1、雙指針算法

用兩個指針來共同解決一個問題：

1.1 對撞雙指針

比如先有一個有序的數組array

int[] array = {1, 4, 5, 7, 9}

先要找兩個數，使得其和為12，且兩個數不能相同。最先想到的是，兩層循環，遍歷array，如外層 i = 1，內層循環 j = 4 5 7 9，外層 i = 4，內層循環 j = 1 5 7 9……，但這樣時間復雜度為O(n^2)。用對撞雙指針優化：

對撞前即p1 <= p2，p1 = p2時，說明二者指向同一個元素，再往下就錯開了。

1.2 快慢雙指針

比如現在要檢測一個鏈表是否為環形：

此時可用快慢雙指針，慢的一次走一步，s = s.next，快的一次走兩步，f = f.next.next，二者同時從隊首出發：

移動三次后，快慢指針相遇了，這說明是個環形，否則二者不會相遇。

2、leetcode141：環形鏈表

和上面的快慢指針一樣，代碼實現：

public class P141 {public static boolean checkCycle(ListNode head) {if (null == head) {return false;}// 快慢指針，均從頭節點開始ListNode slowPoint = head;ListNode fastPoint = head;// 這里的條件無需判斷慢指針，如果是環形，大家都不為null// 如果不是環形，那一定是快指針先走完而出現null// 因此退出循環的條件是：快指針走完了，而快指針一次兩步，所以走完的條件是當前已為空或者不夠兩步了while(fastPoint != null && fastPoint.next != null) {// 慢指針一次一步，快指針一次兩步slowPoint = slowPoint.next;fastPoint = fastPoint.next.next;if (slowPoint.equals(fastPoint)){return true;}}return false;}
}

測試：

//鏈表節點類
public class ListNode {int val;ListNode next;public ListNode() {}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}@Overridepublic String toString() {return "ListNode{" +"val=" + val +", next=" + next +'}';}
}

public class P141 {public static void main(String[] args) {ListNode tailNode = new ListNode(1, null);ListNode node4 = new ListNode(2, tailNode);ListNode node3 = new ListNode(2, node4);ListNode node2 = new ListNode(1, node3);ListNode node1 = new ListNode(0, node2);ListNode head = new ListNode(9, node1);tailNode.setNext(head);System.out.println(checkCycle(head));}
}

3、leetcode881：救生艇

其實本質是兩個人的體重之和問題，和上面提到的對撞指針很像，不過一個是等號，一個是小于號，因此考慮先給所有人的體重從小到大排個序（因為排序是對撞指針移動的基礎前提）

public class P881 {public static int calcMinShipNum (int[] weight, int limit) {if (weight == null || weight.length == 0 || limit <= 0) {return 0;}Arrays.sort(weight);// 頭尾指針的位置int i = 0;int j = weight.length - 1;// 船的數量int res = 0;while (i <= j) {if (weight[i] + weight[j] < limit) {// 兩個人可以乘一條船走，船的數量+1，頭指針向右一位，尾指針向左一位i = i + 1;j = j - 1;} else {// 兩個人體重總和超重，只讓最胖的人走j = j - 1;}// 不管這輪是載走了首位兩個人，還是只能帶走最胖的那個人，船的數量都+1res = res + 1;}return res;}
}

測試：

public class P881 {public static void main(String[] args) {int[] weightArray = {3,5,3,4};System.out.println(calcMinShipNum(weightArray, 5));}
}