一、滑動窗口模板問題類型典型題干關鍵詞固定長度例題1. 最長/最短子數組滿足某條件“最長”“最短”“連續”可變最長無重復子串、最短覆蓋子串2. 固定長度子數組統計“長度為 k 的連續”固定長度為 k 的最大平均值、固定大小子數組的最大和3. 計數/是否存在滿足條件的子數組“是否存在”“共有多少個”均可和等于目標值的子數組個數4. 兩個子數組/字符串比較“兩個”“相等”均可找到字符串中所有字母異位詞模板求滿足條件的最短/最長/計數子數組子串 數組正數、負數、零都通用按需改 while 條件即可 public int slideWindow(int[] nums, int k) { int left 0, ans 0; // 1. 答案變量按需改 int sum 0; // 2. 維護窗口指標和、計數、哈希表… for (int right 0; right nums.length; right) { sum nums[right]; // 3. 右邊界右移擴大窗口 while (left right 滿足收縮條件) { // 4. 需要收縮就循環 更新答案; // 5. 在收縮前更新最短/計數等 sum - nums[left]; // 6. 去掉頭元素 left; // 7. 左邊界右移窗口縮小 } 更新答案; // 8. 也可以在擴張后更新最長/計數等 } return ans; }二、哈希表HashSetInteger set new HashSet();場景關鍵詞例題快速查找是否存在、下標、次數兩數之和、LRU、字母異位詞去重重復、唯一最長無重復子串計數出現次數、頻率前 K 個高頻元素映射鍵值對應羅馬數字轉整數import java.util.HashSet; import java.util.Set; public class TwoSum { 判斷數組中是否存在兩個元素使得它們的和等于 target param nums 輸入數組 param target 目標和 return true 表示存在這樣兩個元素false 表示不存在 public static boolean hasTwoSum(int[] nums, int target) { //創建一個哈希集合用來存放“已經遍歷過的數字”HashSet 基于哈希表實現 SetInteger seen new HashSet(); // 2. 從頭到尾掃描數組 for (int num : nums) { // 3. 計算當前數字 num 所需要的“另一半” int complement target - num; // 4. 在常數時間內查哈希表另一半是否出現過 if (seen.contains(complement)) { // 5. 出現過說明 num complement target任務完成 return true; } // 6. 否則把當前數字加入哈希表供后面的數字使用 seen.add(num); } // 7. 掃完整個數組都沒找到返回 false return false; } // 簡單測試 public static void main(String[] args) { int[] nums {2, 7, 11, 15}; int target 9; System.out.println(hasTwoSum(nums, target)); // 輸出 true因為 279 } }三、判斷字母出現的次數String s HelloWorld.toLowerCase(); int[] freq new int[26]; // 0 對應 a25 對應 z for (char c : s.toCharArray()) { if (c a c z) { // 過濾非字母 freq[c - a]; } } // 打印示例 for (int i 0; i 26; i) { if (freq[i] 0) System.out.println((char) (i a) : freq[i]); }判斷兩字符串每個字母出現次數是否相同public static boolean sameLetterCount(String s1, String s2) { int[] cnt1 countLetters(s1); int[] cnt2 countLetters(s2); return Arrays.equals(cnt1, cnt2); // Java 內置數組比較 } private static int[] countLetters(String s) { int[] freq new int[26]; for (char c : s.toLowerCase().toCharArray()) { if (c a c z) { // 忽略非字母 freq[c - a]; } } return freq; }四、判斷重復元素HashSetInteger set new HashSet()HashSetInteger set new HashSet(); 這段代碼創建了一個用于存儲整數的集合這個集合會自動去除重復的元素。它主要用在以下幾種常見的場景1. 需要去除重復元素時 當你從某個數據源如數組、列表等讀取數據但不希望其中有重復的元素時可以使用 HashSetset.add(number);2. 需要快速判斷某個元素是否已存在時set.add(i);3. 實現一些算法問題時 例如在“快樂數”問題中用來記錄已經計算過的數字以檢測是否存在循環set.add(n);4. 實現簡單的緩存功能時當你需要一個簡單的緩存來存儲最近訪問過的元素并且希望快速判斷某個元素是否已經在緩存中時set.add(someValue);判斷元素是否在緩存中5. 實現集合運算時set1.retainAll(set2);6.!set.add(nums[i]) 如果nums[i]已經在集合中則返回 true表示數組中存在重復元素。五、二維數組1.排序// 1. 按起點升序 Arrays.sort(intervals, (a, b) - a[0] - b[0]); //示例 int[][] intervals {{5,10}, {1,3}, {2,6}}; Arrays.sort(intervals, (a, b) - a[0] - b[0]); 結果[[1,3], [2,6], [5,10]]2.二維數組 ? List 互轉// 數組 → List Listint[] list Arrays.asList(a); // 注意大小固定不能增刪 // 數組 → 可變 List Listint[] list2 new ArrayList(Arrays.asList(a)); // List → 數組 int[][] arr list.toArray(new int[0][]);3.合并重疊區間Arrays.sort(a, (x,y)-Integer.compare(x[0],y[0])); Listint[] m new ArrayList(); for (int[] p : a) { if (m.isEmpty() || m.get(m.size()-1)[1] p[0]) m.add(p); else m.get(m.size()-1)[1] Math.max(m.get(m.size()-1)[1], p[1]); } int[][] merged m.toArray(int[][]::new);4.插入區間階段區間特征動作① 左邊intervals[i].end newInterval.start舊區間的尾和新區間插入的頭完全在左側無交集直接丟進答案② 中間有交集start ≤ newInterval.end end ≥ newInterval.start不斷合并把 newInterval 擴成 [min(start)③ 右邊intervals[i].start newInterval.end舊區間的頭和新插入區間的尾完全在右側無交集直接丟進答案public int[][] insert(int[][] intervals, int[] newInterval) { Listint[] res new ArrayList(); int i 0, n intervals.length; // 階段①左邊無交集 while (i n intervals[i][1] newInterval[0]) { res.add(intervals[i]); } // 階段②中間有交集不斷合并 while (i n intervals[i][0] newInterval[1]) { newInterval[0] Math.min(newInterval[0], intervals[i][0]); newInterval[1] Math.max(newInterval[1], intervals[i][1]); i; } res.add(newInterval); // 合并后的唯一區間 // 階段③右邊無交集 while (i n) { res.add(intervals[i]); } return res.toArray(new int[res.size()][]); }六、棧StackCharacter stack new Stack();場景關鍵詞例題括號/標簽匹配最近匹配、成對出現有效的括號、HTML 標簽表達式求值后綴/中綴、運算符優先級基本計算器DFS 非遞歸回溯、路徑二叉樹中序遍歷非遞歸單調性維護下一個更大元素、溫度每日溫度、接雨水中文術語等價代碼返回值說明壓棧入棧stack.push(E) 或 stack.addLast(E)void把元素放到棧頂彈棧出棧stack.pop() 或 stack.removeLast()E移除并返回棧頂空時拋 NoSuchElementException只看棧頂stack.peek() 或 stack.peekLast()E不刪除空時返回 null判空stack.isEmpty()boolean空返回 true獲取大小stack.size()int當前元素個數清空stack.clear()void一鍵變空棧是否包含stack.contains(o)boolean從棧頂到棧底順序找迭代for (E e : stack)—從棧底→棧頂順序七、鏈表1.鏈表的遍歷for (Node p head; p ! null; p p.next) { // 每次循環里 p 指向當前節點 }2.鏈表的常用方法操作代碼示例說明遍歷for (Node p head; p ! null; p p.next)從頭掃到尾新建節點Node node new ListNode(val);生成新節點后插node.next nextNode;把當前節點指向下一節點隨機指針node.random randomNode;隨機鏈表獨有頭插法node.next head; head node;新節點變新頭計數int cnt 0;for (Node p head; p ! null; p p.next) cnt;統計節點個數反轉三指針迭代 / 遞歸經典高頻題合并有序雙指針歸并見前面“合并兩條有序鏈表”?Map 的常用方法復制隨機鏈表時用MapNode, Node map new HashMap();方法代碼示例作用put(K key, V value)map.put(oldNode, newNode);存鍵值對get(Object key)Node n map.get(oldNode);根據鍵拿值containsKey(Object key)if (map.containsKey(node))判斷鍵是否存在remove(Object key)map.remove(node);刪除鍵值對clear()map.clear();清空表map使用場景場景關鍵詞示例題目Map 用法隨機指針深拷貝復制帶隨機指針鏈表原節點 → 新節點快速查找/判重兩數之和、最長無重復子串值 → 下標計數/頻率前 K 個高頻元素、字母異位詞分組元素 → 出現次數映射關系羅馬數字轉整數、13 號羅馬羅馬字符 → 數值分組按出現次數排序、字母異位詞key 設計為“簽名”緩存/記憶化遞歸加緩存DP 備忘錄參數 → 計算結果? 反面教材別濫用只是順序遍歷 → 用 List/數組只要兩頭操作 → 用 Deque只要排序 → 用 TreeSet/優先隊列八、樹和二叉樹1.二叉樹的翻轉遞歸實現 class TreeNode { int val;//給每個節點存一個整數值 TreeNode left, right; TreeNode(int x) { val x; }//新建節點時一次性把值填進去。 } public class Solution { // 主接口 public TreeNode invertTree(TreeNode root) { if (root null) return null; // 交換左右子樹 TreeNode tmp root.left; root.left root.right; root.right tmp; // 遞歸處理子樹 invertTree(root.left); invertTree(root.right); return root; } }2.獲取節點值System.arraycopy 把一段數組里的元素快速拷貝到另一段數組里System.arraycopy(源數組, 源起始下標, 目標數組, 目標起始下標, 復制長度);// 4. 新建 4 個小數組左前序、左中序、右前序、右中序 int[] leftPre new int[leftSize];//左子樹的前序 int[] leftIn new int[leftSize];//左子樹的中序 int[] rightPre new int[rightSize];//右子樹的前序 int[] rightIn new int[rightSize];//右子樹的中序 //開始拿數據 //從第 1 個開始拿leftSize個 → 就是左子樹的前序。 System.arraycopy(preorder, 1, leftPre, 0, leftSize); //中序里根左邊正好leftSize個元素 → 左子樹的中序。 System.arraycopy(inorder, 0, leftIn, 0, leftSize); //前序里根后面先走左子樹再走右子樹所以右子樹從1 leftSize開始拿。 System.arraycopy(preorder, 1 leftSize, rightPre, 0, rightSize); //中序里根右邊所有元素 → 右子樹的中序 System.arraycopy(inorder, rootPos 1, rightIn, 0, rightSize);3.前序和中序構建二叉樹//前序負責找根中序負責分左右。中序遍歷根的下標值就是左子樹個數。 class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { // 邊界 if (preorder.length 0) return null; // 1. 前序第 0 個就是根 int rootVal preorder[0]; TreeNode root new TreeNode(rootVal); // 2. 在中序里找根的位置 int rootPos 0; for (int i 0; i inorder.length; i) { if (inorder[i] rootVal) { rootPos i;//記錄下根節點的值的下標 break; } } // 3. 切成左、右兩份 int leftSize rootPos; // 左子樹節點個數中序遍歷根的下標值就是左子樹個數 int rightSize inorder.length - leftSize - 1; // 4. 新建 4 個小數組左前序、左中序、右前序、右中序 int[] leftPre new int[leftSize];//左子樹的前序 int[] leftIn new int[leftSize];//左子樹的中序 int[] rightPre new int[rightSize];//右子樹的前序 int[] rightIn new int[rightSize];//右子樹的中序 //開始拿數據 System.arraycopy(preorder, 1, leftPre, 0, leftSize); System.arraycopy(inorder, 0, leftIn, 0, leftSize); System.arraycopy(preorder, 1 leftSize, rightPre, 0, rightSize); System.arraycopy(inorder, rootPos 1, rightIn, 0, rightSize); // 5. 遞歸搭左、右子樹 root.left buildTree(leftPre, leftIn); root.right buildTree(rightPre, rightIn); return root; } }4.中序和后序構建二叉樹后序找根中序分左右1. 后序最后一個元素就是根2. 去中序里找到這個根左邊全是左子樹右邊全是右子樹3. 根據左子樹長度把后序也切成左、右兩份4. 對左右兩份重復 1→2→3直到分空/*后序找根中序分左右 */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { //用遞歸函數處理整棵樹的區間 return build(inorder, 0, inorder.length - 1,//中序從 0 號到末尾 postorder, 0, postorder.length - 1);//后序從 0 號到末尾 } // il..ir 中序區間pl..pr 后序區間 //in是原始中序數組post是原始后序數組 private TreeNode build(int[] in, int il, int ir, int[] post, int pl, int pr) { if (il ir) return null; int rootVal post[pr]; //后序最后一個就是根 TreeNode root new TreeNode(rootVal); // 在中序里找根 int rootPos il; while (in[rootPos] ! rootVal) rootPos; int leftSize rootPos - il; //左子樹節點個數 root.left build(in, il, rootPos - 1, post, pl, pl leftSize - 1); root.right build(in, rootPos 1, ir, post, pl leftSize, pr - 1); return root; } }5.獲取完全二叉樹的節點個數class Solution { public int countNodes(TreeNode root) { if(root null){ return 0; } int left countLevel(root.left); int right countLevel(root.right); if(left right){ return countNodes(root.right) (1left); }else{ return countNodes(root.left) (1right); } } private int countLevel(TreeNode root){ int level 0; while(root ! null){ level; root root.left; } return level; } }