大廠算法面試之leetcode精講7.雙指針
視頻教程（高效學習）:點擊學習
目錄：
雙指針
- 普通指針：兩指針同一方向或不同方向
- 對撞指針：兩指針互相靠攏
- 快慢指針：一快一慢
141. 環形鏈表 (easy)
方法1.哈希表或set:
- 思路：準備一個map或者set，然后循環鏈表，每次遍歷到一個節點的時候，判斷當前節點是否在map中存在，如果不存在就把當前節點加入map中，如果存在的話說明之前訪問過此節點，也就說明了這條鏈表有環。
- 復雜度分析：時間復雜度
O(n)，n是鏈表的數量，最差的情況下每個節點都要遍歷。空間復雜度O(n)，n是存儲遍歷過的節點的map或者set
js:
var hasCycle = (head) => { let map = new Map(); while (head) { if (map.has(head)) return true;//如果當前節點在map中存在就說明有環 map.set(head, true);//否則就加入map head = head.next;//迭代節點 } return false;//循環完成發現沒有重復節點，說明沒環};java:
public class Solution { public boolean hasCycle(ListNode head) { Set seen = new HashSet(); while (head != null) { if (!seen.add(head)) { return true; } head = head.next; } return false; }} 方法2.快慢指針
- 思路：準備兩個指針fast和slow，循環鏈表，slow指針初始也指向head，每次循環向前走一步，fast指針初始指向head，每次循環向前兩步，如果沒有環，則快指針會抵達終點，如果有環，那么快指針會追上慢指針
- 復雜度：時間復雜度
O(n)，空間復雜度O(1)
js:
var hasCycle = function (head) { //設置快慢指針 let slow = head; let fast = head; //如果沒有環，則快指針會抵達終點，否則繼續移動雙指針 while (fast && fast.next) { slow = slow.next; fast = fast.next.next; //快慢指針相遇，說明含有環 if (slow == fast) { return true; } } return false;};java:
public class Solution { public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { return true; } } return false; }}142. 環形鏈表 II (medium)
方法1.哈希表
- 思路：遍歷鏈表，將節點加入一個set中，每次判斷當前節點是否在set中，如果存在重復的節點，這個節點就是入環節點
- 復雜度：時間復雜度
O(n)，空間復雜度O(n)
js：
var detectCycle = function(head) { const visited = new Set(); while (head !== null) {//終止條件，如果沒有環 跳出循環 if (visited.has(head)) {//如果存在重復的節點，這個節點就是入環節點 return head; } visited.add(head);//將節點加入set中 head = head.next; } return null;};java：
public class Solution { public ListNode detectCycle(ListNode head) { ListNode pos = head; Set visited = new HashSet(); while (pos != null) { if (visited.contains(pos)) { return pos; } else { visited.add(pos); } pos = pos.next; } return null; }} 方法2.快慢指針
- 思路：慢指針移動兩步，快指針移動一步，相遇之后，快指針變成頭指針，然后每次快慢指針各走一步直到相遇，相遇的節點就是入環節點
- 復雜度：時間復雜度
O(n)，空間復雜度O(1)
js：
var detectCycle = function(head) { if (head === null) { return null; } let slow = head, fast = head; while (fast !== null) { slow = slow.next;//慢指針移動兩步，快指針移動一步 if (fast.next !== null) { fast = fast.next.next; } else { return null;//如果沒有環 之間返回null } if (fast === slow) {//有環 let fast = head; //快指針指向頭節點，然后每次快慢指針各走一步直到相遇，相遇的節點就是入環節點 while (fast !== slow) { fast = fast.next; slow = slow.next; } return fast; } } return null;};java：
public class Solution { public ListNode detectCycle(ListNode head) { if (head == null) { return null; } ListNode slow = head, fast = head; while (fast != null) { slow = slow.next; if (fast.next != null) { fast = fast.next.next; } else { return null; } if (fast == slow) { ListNode fast1 = head; while (fast1 != slow) { fast1 = fast1.next; slow = slow.next; } return fast1; } } return null; }}15. 三數之和 (medium)
方法1.暴力求解，對于三個數字，循環3次，分別計算和，時間復雜度O(n^3)
方法2.c=-(a+b): 確定了a和b，那就可以想兩數之和一樣，在map中尋找-(a+b)，減少一層循環，時間復雜度O(n^2)，空間復雜度O(n)。
方法3.排序然后查找
- 思路：先排序數組，數組長度必須大于3，循環數組，假如當前循環到了i索引，則定義兩個指針
L = i+1，和R = nums.length-1,如果和sum=nums[i] + nums[L] + nums[R]小于0，則向右移動左指針，如果sum大于0，則左移右指針，如果sum等于0，則正好找到了這3個數，然后在嘗試L++,R--，繼續尋找中間是否有三個數之和等于0，注意在循環的過程中遇見相同的三個數需要去重。 - 復雜度分析：時間復雜度
O(n^2)，n為數組的長度。空間復雜度O(logn)，即排序所需要的空間
js:
var threeSum = function(nums) { let ans = []; const len = nums.length; if(nums == null || len < 3) return ans;//數組的長度大于3 nums.sort((a, b) => a - b); // 排序 for (let i = 0; i < len ; i++) { if(nums[i] > 0) break; // 如果當前數字大于0，則三數之和一定大于0，所以結束循環 if(i > 0 && nums[i] == nums[i-1]) continue; // 去重 let L = i+1; let R = len-1; while(L < R){//雖然里面還有兩個循環，但是整體的L和R移動的時間內復雜度還是o(n) const sum = nums[i] + nums[L] + nums[R]; if(sum == 0){ ans.push([nums[i],nums[L],nums[R]]); while (L 0) R--; } } return ans;}; java:
class Solution { public static List> threeSum(int[] nums) { List> ans = new ArrayList(); int len = nums.length; if(nums == null || len < 3) return ans; Arrays.sort(nums); for (int i = 0; i < len ; i++) { if(nums[i] > 0) break; // 如果當前數字大于0，則三數之和一定大于0，所以結束循環 if(i > 0 && nums[i] == nums[i-1]) continue; // 去重 int L = i+1; int R = len-1; while(L < R){ int sum = nums[i] + nums[L] + nums[R]; if(sum == 0){ ans.add(Arrays.asList(nums[i],nums[L],nums[R])); while (L 0) R--; } } return ans; }} 11. 盛最多水的容器 （medium）
方法1:雙指針
- 思路：用雙指針i，j循環height數，i，j對應高度較小的那個先向內移動，不斷計算面積，更新最大面積
- 復雜度：時間復雜度
O(n)，n是數組height的長度，遍歷一次。空間復雜度O(1)
js：
var maxArea = function(height) { let max = 0; for (let i = 0, j = height.length - 1; i < j;) {//雙指針i，j循環height數組 //i，j較小的那個先向內移動 如果高的指針先移動，那肯定不如當前的面積大 const minHeight = height[i] < height[j] ? height[i++] : height[j--]; const area = (j - i + 1) * minHeight;//計算面積 max = Math.max(max, area);//更新最大面積 } return max;};java：
class Solution { public int maxArea(int[] height) { int i = 0, j = height.length - 1, max = 0; while(i < j) { max = height[i] < height[j] ? Math.max(max, (j - i) * height[i++]): Math.max(max, (j - i) * height[j--]); } return max; }}160. 相交鏈表 （easy）
方法1:哈希表
- 思路：將鏈表A存入set中，第一個相同的節點就是重合的節點
- 復雜度：時間復雜度
O(m+n)，m、n分別是兩個鏈表的長度。空間復雜度O(m)
js：
var getIntersectionNode = function(headA, headB) { const visited = new Set(); let temp = headA; while (temp !== null) {//將鏈表A存入set中 visited.add(temp); temp = temp.next; } temp = headB; while (temp !== null) { if (visited.has(temp)) {//第一個相同的節點就是重合的節點 return temp; } temp = temp.next; } return null;};Java：
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set visited = new HashSet(); ListNode temp = headA; while (temp != null) { visited.add(temp); temp = temp.next; } temp = headB; while (temp != null) { if (visited.contains(temp)) { return temp; } temp = temp.next; } return null; }} 方法2:雙指針
- 思路：用雙指針pA 、pB循環倆個鏈表，鏈表A循環結束就循環鏈表B，鏈表A循環結束就循環鏈表B，當
pA == pB時就是交點，因為兩個指針移動的步數一樣 - 復雜度：時間復雜度
O(m+n)，m、n分別是兩個鏈表的長度。空間復雜度O(1)
js：
var getIntersectionNode = function(headA, headB) { if (headA === null || headB === null) { return null; } let pA = headA, pB = headB; while (pA !== pB) { pA = pA === null ? headB : pA.next;//鏈表A循環結束就循環鏈表B pB = pB === null ? headA : pB.next;//鏈表A循環結束就循環鏈表B } return pA;//當pA == pB時就是交點};java:
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode pA = headA, pB = headB; while (pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; }}876. 鏈表的中間結點（easy)
- 思路：快慢指針遍歷，直到快指針到達最后
- 復雜度：時間復雜度
O(n)，空間復雜度O(1)
js：
var middleNode = function(head) { slow = fast = head; while (fast && fast.next) {//快慢指針遍歷，直到快指針到達最后 slow = slow.next; fast = fast.next.next; } return slow;};java：
class Solution { public ListNode middleNode(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }}
