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