LeetCode面試官泄露：14個模板覆蓋95%算法題

北美大廠算法面試有個公開的秘密：有人刷了400題掛掉Google，有人只練80題拿到5個offer。差距不在題量，在是否提前看過"考綱"。

LeetCode現存3000+題目，但面試高頻考點高度收斂。前Google工程師、現Meta技術面試官整理了一份內部流傳的模式清單——14個代碼模板，覆蓋95%的面試題型。這不是投機取巧，是把O(n2)的暴力解法壓縮成O(n)的系統工程。

雙指針：從兩頭往中間夾

數組或字符串里找配對、比大小、做分割，第一反應應該是雙指針。left從0出發，right從末尾往回走，每次循環干掉一半搜索空間。

經典場景：Two Sum（有序數組版）、盛最多水的容器、驗證回文串、三數之和。模板核心就五行——初始化、循環、比較、收縮左邊界、收縮右邊界。

關鍵認知：雙指針的本質是用空間換時間的反向操作。不建哈希表，用兩個游標消除內層循環，把平方復雜度壓成線性。

一個細節：三數之和的去重邏輯容易寫錯。排序后，當left右移時如果下一個數和當前相同，要跳過；right同理。這個去重比算法本身更容易掛面試。

滑動窗口：子數組問題的通用框架

求"滿足某條件的連續子數組"，比如最大和、最長無重復字符、最小覆蓋子串——全是滑動窗口的領地。

模板分兩種。固定窗口大?。河疫呥M一個，左邊出一個，保持窗口恒定。可變窗口：右邊一直擴，直到違反約束，再從左邊收縮到合法。

代碼骨架是四層嵌套：外層遍歷右邊界、更新窗口狀態、內層while收縮左邊界、更新結果。窗口狀態通常用哈希表或數組計數，面試時先寫偽代碼確認面試官要的是固定還是可變。

高頻翻車點：Minimum Window Substring要求覆蓋所有目標字符，不是任意k個。很多候選人把"至少k個不同字符"和"覆蓋目標串"搞混，20分鐘直接歸零。

快慢指針：鏈表問題的作弊器

鏈表沒法隨機訪問，但快慢指針給了你一個"偽二分"的能力。slow走一步，fast走兩步，fast到終點時slow正好在中點。

判環、找中點、檢測快樂數，同一個模板改兩行就能用。判環時相遇即存在環；找中點時返回slow；快樂數把數字替換成各位平方和，重復即環。

Meta去年秋招的follow-up：如果鏈表有環，找到環的入口點。這需要數學推導——相遇后把slow拉回head，同步走再次相遇即為入口。能現場推出來的，評級直接升一檔。

區間合并：日程表沖突的標準解法

會議室預定、日程合并、區間插入，本質都是同一道題：先按起點排序，然后遍歷，要么合并（當前起點≤上一個終點），要么新開區間。

Meeting Rooms II的變種問"最多需要幾間會議室"——用最小堆存每個會議的結束時間，新會議開始時間≥堆頂則復用房間，否則開新房間。堆的大小就是答案。

這個模式在Google面試出現頻率極高，因為和實際系統設計的負載均衡問題同源。能講出"這相當于找最大并發數"的候選人，會被標記為"有系統思維"。

循環排序：原地排序的野路子

數組數值范圍在1到n之間，要求O(n)時間、O(1)空間——循環排序是唯一解。把每個數放到它該去的位置（nums[i]應該放在索引nums[i]-1處），放不下的就是缺失或重復的。

Find the Missing Number、Find the Duplicate Number、Find All Duplicates，全是這個套路。代碼模板是while循環：當前數不在正確位置，就和正確位置的數交換。

易錯點：交換后不能i++，要繼續檢查換過來的數。很多人慣性寫i++，漏掉連鎖反應，調試半小時。

鏈表反轉：遞歸迭代的兩種人格

反轉鏈表是面試的"hello world"，但follow-up能無限深挖。K個一組反轉、部分反轉、兩兩交換，全是同一模板的變體。

迭代版：三個指針prev、curr、next，逐節點后移。遞歸版：遞歸到末尾，返回時逐個翻轉指向。遞歸版代碼更短，但空間O(n)，面試官會問能不能優化。

Amazon的變態考法：用O(1)空間反轉m到n之間的部分。需要先用雙指針走到m-1位置，再套用標準反轉模板，最后拼接三段。能一次寫對的，近兩年內見過的不超過10個。

樹的雙遍歷：前序+中序/后序重建

給兩種遍歷序列重建二叉樹，是考察遞歸思維的試金石。前序+中序、后序+中序可以唯一確定樹，前序+后序不行（除非滿二叉樹）。

模板核心：前序/后序的第一個/最后一個元素是根，在中序里找到根的位置，左邊是左子樹，右邊是右子樹。遞歸構建，用哈希表存中序索引避免重復掃描。

時間復雜度O(n)，空間O(n)存哈希表。面試官常問的優化：如果數組很大，能不能流式處理？答案是只能預處理，因為必須知道左右子樹的邊界才能遞歸。

層級遍歷：BFS的隊列美學

樹的按層打印、找最淺葉子、連接同層節點，全是BFS的領地。用隊列，每層記錄size，內層循環處理完當前層再進下一層。

Binary Tree Level Order Traversal的變形：之字形打印、找每行最大值、判斷完全二叉樹。模板不變，變的是內層循環里對節點的操作。

Google的陷阱題：用DFS實現層級遍歷。需要記錄深度，按深度把節點塞進結果數組的對應位置。能切換兩種思路的，說明理解了遍歷的本質區別。

子集模式：回溯的暴力美學

求所有子集、排列、組合，回溯是通用解。模板是遞歸函數里：做選擇、遞歸、撤銷選擇。子集問題選或不選當前元素，排列問題選哪個位置放當前元素。

去重是難點。有重復元素時，先排序，然后跳過同一層已經用過的相同元素。這個"同一層"和"同一支"的區別，90%的候選人講不清楚。

Subset Sum問是否存在和為target的子集，可以用回溯剪枝，也可以用動態規劃。面試時先問數據范圍，n≤20用回溯，n≥100必須用DP，選錯直接超時。

二分變種：找邊界、找旋轉、找答案

二分查找不只是找目標值。找第一個≥target的位置、找最后一個≤target的位置、找旋轉數組的最小值、找峰值元素——全是二分模板的變形。

核心不變：確定搜索區間[left, right]還是[left, right)，確定中間點比較后收縮哪邊，確定終止條件和返回值。旋轉數組的關鍵是判斷哪半邊有序，然后在有序半邊判斷target是否在范圍內。

Search in Rotated Sorted Array的follow-up：有重復元素怎么辦？最壞情況退化成O(n)，但平均還是O(log n)。能分析出這個的，算法基礎分拿滿。

拓撲排序：有向圖的依賴解析

課程表、編譯順序、任務調度，全是拓撲排序。Kahn算法（BFS）或DFS記錄后序遍歷，兩種實現都要會。

Kahn算法：計算入度，入度為0的入隊，逐個彈出并減少鄰居入度。DFS版：遞歸訪問所有鄰居，訪問完把當前節點壓棧，最后逆序就是拓撲序。

檢測環是隱藏考點。Kahn算法最后如果還有節點沒訪問，說明有環；DFS版用三色標記（未訪問/訪問中/已訪問），遇到訪問中節點即環。

并查集：連通性的O(α(n))解法

朋友圈、省份數量、冗余連接、島嶼數量II——動態連通性問題，并查集是標準答案。路徑壓縮+按秩合并，時間復雜度接近常數。

模板四件套：find（帶路徑壓縮）、union（按秩合并）、初始化、計數。面試時先寫樸素版，面試官要求優化再補上壓縮和合并。

LeetCode 305島嶼數量II的trick：從全是水的網格逐步添加陸地，每添加一個檢查四鄰居，用并查集維護連通分量數。能想到并查集的，已經跑贏80%的候選人。

前綴和：子數組求和的降維打擊

求和為k的子數組個數、和為k的最大長度、二維區域和檢索——前綴和把區間查詢變成O(1)。

一維：presum[i] = sum(nums[0..i-1])，區間和= presum[j+1] - presum[i]。二維：presum[i][j]存左上角(0,0)到(i-1,j-1)的和，容斥原理算任意矩形。

和為k的子數組個數，用哈希表存前綴和出現次數，當前前綴和-k的次數就是以當前結尾的合法子數組數。這個"當前-目標=歷史"的思路，和兩數之和的哈希表解法同源。

動態規劃：最后一塊拼圖

DP是獨立大類，但面試高頻的其實就幾種：線性DP（爬樓梯、打家劫舍）、區間DP（石子合并、最長回文子序列）、背包DP（01背包、完全背包）、樹形DP（打家劫舍III）、狀態壓縮DP（旅行商問題，極少考）。

線性DP的模板：dp[i]表示以i結尾的最優解，狀態轉移看i-1、i-2或某個前綴。背包問題的模板：二維dp[i][j]表示前i個物品容量j的最大價值，優化成一維要倒序遍歷容量。

面試技巧：先寫暴力遞歸，加記憶化，再改迭代。這個過程展示思維路徑，比直接寫DP得分更高。

這14個模式不是終點。真正的高手會在模板基礎上變形——雙指針擴展到多指針，滑動窗口加上單調隊列，BFS換成雙向BFS。但變形的前提是模板已經刻進肌肉記憶。

一個數據點：2024年北美大廠算法面試中，這14個模式的原題或變體出現頻率超過90%。剩下的10%是設計題或罕見題型，不影響hire/no hire的決定。