🔹 数组（Array）

1. 两数之和

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int diff = target - nums[i];
        if (map.containsKey(diff)) {
            return new int[]{map.get(diff), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

2. 最大子数组和（Kadane 算法）

public int maxSubArray(int[] nums) {
    int max = nums[0], cur = nums[0];
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);
        max = Math.max(max, cur);
    }
    return max;
}

🔹 链表（Linked List）

1. 反转链表

public ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

2. 判断链表是否有环（快慢指针）

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

🔹 栈 / 队列

1. 有效括号

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

2. 用栈实现队列

class MyQueue {
    Stack<Integer> in = new Stack<>();
    Stack<Integer> out = new Stack<>();
    public void push(int x) { in.push(x); }
    public int pop() { peek(); return out.pop(); }
    public int peek() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

🔹 二叉树

1. 二叉树的遍历（递归 & 迭代）

// 前序遍历
public void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

// 层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

2. 验证二叉搜索树

public boolean isValidBST(TreeNode root) {
    return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean helper(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return helper(node.left, min, node.val) && helper(node.right, node.val, max);
}

🔹 堆 / 优先队列

1. 数组中的第 K 大元素

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int n : nums) {
        pq.offer(n);
        if (pq.size() > k) pq.poll();
    }
    return pq.peek();
}

🔹 图

1. 图的 BFS

public void bfs(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        for (int nei : graph.get(node)) {
            if (!visited[nei]) {
                visited[nei] = true;
                queue.offer(nei);
            }
        }
    }
}

2. 岛屿数量（DFS）

public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}
private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
    grid[i][j] = '0';
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

🔹 排序算法

快速排序

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left], i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) i++;
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

🔹 动态规划（DP）

1. 爬楼梯（斐波那契）

public int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2, res = 0;
    for (int i = 3; i <= n; i++) {
        res = a + b;
        a = b;
        b = res;
    }
    return res;
}

2. 最长公共子序列（LCS）

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

高级

先给两个通用辅助类（很多题会用到）：ListNode（链表节点）和 TreeNode（二叉树节点）。

// 通用辅助类
class ListNode {
    int val;
    ListNode next;
    ListNode(int v) { val = v; }
}
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

目录（快速跳转）

数组 / 双指针 / 滑动窗口 / 前缀和
排序 / 选择（Quickselect）
链表进阶
栈进阶 / 单调栈
队列 / 双端队列（滑动窗口最大值）
堆（合并 K 表、数据流中位数）
树（序列化/反序列化、LCA、最大路径和）
图（拓扑、Dijkstra、Bellman-Ford、并查集）
动态规划（LIS、背包、DP 状态压缩等）
回溯（N 皇后、组合/子集变体）
字符串（KMP、Rabin-Karp、最小覆盖子串）
字典树 Trie
线段树 / 树状数组（Fenwick）
位运算 / 数学小技巧
设计题（LRU Cache）

1. 数组 / 双指针 / 滑动窗口 / 前缀和

1.1 最长不含重复字符的子串（LeetCode 3）

思路：滑动窗口 + 哈希表记录字符上次出现位置。
复杂度：O(n) 时间，O(min(n, charset)) 空间。

public int lengthOfLongestSubstring(String s) {
    int[] last = new int[128]; // ASCII
    Arrays.fill(last, -1);
    int start = 0, maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        start = Math.max(start, last[c] + 1);
        maxLen = Math.max(maxLen, i - start + 1);
        last[c] = i;
    }
    return maxLen;
}

1.2 最小覆盖子串（LeetCode 76）

思路：滑动窗口 + 计数表；需要满足条件时收缩左边界。
复杂度：O(n)。

public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int left = 0, right = 0, required = t.length(), minLen = Integer.MAX_VALUE, start = 0;
    while (right < s.length()) {
        char c = s.charAt(right++);
        if (need[c]-- > 0) required--;
        while (required == 0) {
            if (right - left < minLen) { minLen = right - left; start = left; }
            char d = s.charAt(left++);
            if (need[d]++ >= 0) required++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

1.3 子数组和等于 k（LeetCode 560）

思路：前缀和 + 哈希表记录之前出现的前缀和频次。
复杂度：O(n)。

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    int sum = 0, res = 0;
    for (int x : nums) {
        sum += x;
        res += cnt.getOrDefault(sum - k, 0);
        cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
    }
    return res;
}

1.4 三数之和最接近（LeetCode 16）

思路：排序 + 双指针。复杂度 O(n^2)。

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int closest = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
        int l = i + 1, r = nums.length - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (Math.abs(sum - target) < Math.abs(closest - target)) closest = sum;
            if (sum > target) r--;
            else if (sum < target) l++;
            else return target;
        }
    }
    return closest;
}

2. 排序 / 选择 (Quickselect)

2.1 Quickselect：第 k 小 / 第 k 大

思路：类似快速排序 partition，期望线性时间。
复杂度：平均 O(n)，最坏 O(n^2)。

public int quickSelect(int[] nums, int k) { // 1-based k-th smallest
    return quickSelect(nums, 0, nums.length - 1, k - 1);
}
private int quickSelect(int[] a, int l, int r, int k) {
    if (l == r) return a[l];
    int pivot = partition(a, l, r);
    if (k == pivot) return a[k];
    else if (k < pivot) return quickSelect(a, l, pivot - 1, k);
    else return quickSelect(a, pivot + 1, r, k);
}
private int partition(int[] a, int l, int r) {
    int pivotVal = a[r], i = l;
    for (int j = l; j < r; j++) {
        if (a[j] <= pivotVal) swap(a, i++, j);
    }
    swap(a, i, r);
    return i;
}
private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

3. 链表进阶

3.1 反转 k 个一组（LeetCode 25）

思路：分段反转。复杂度 O(n)。

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0), prev = dummy;
    dummy.next = head;
    while (true) {
        ListNode node = prev;
        for (int i = 0; i < k && node != null; i++) node = node.next;
        if (node == null) break;
        ListNode tail = prev.next, curr = tail.next;
        for (int i = 1; i < k; i++) {
            tail.next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = tail.next;
        }
        prev = tail;
    }
    return dummy.next;
}

3.2 链表排序（归并排序，LeetCode 148）

思路：递归分治，O(n log n) 时间，O(log n) 递归栈空间。

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow.next; slow.next = null;
    return merge(sortList(head), sortList(mid));
}
private ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), p = dummy;
    while (a != null && b != null) {
        if (a.val < b.val) { p.next = a; a = a.next; }
        else { p.next = b; b = b.next; }
        p = p.next;
    }
    p.next = (a != null) ? a : b;
    return dummy.next;
}

3.3 环的入口（LeetCode 142）

思路：Floyd 快慢指针，找到相遇点后从头与相遇点同步移动。复杂度 O(n)。

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
        if (slow == fast) {
            ListNode p = head;
            while (p != slow) { p = p.next; slow = slow.next; }
            return p;
        }
    }
    return null;
}

4. 栈进阶 / 单调栈

4.1 单调栈模板（解决最近更大/更小元素、直方图最大矩形等）

思路：维护单调递增或递减栈（存下标）。复杂度 O(n)。

// 以寻找每个元素右侧第一个大于它的下标为例
public int[] nextGreaterIndices(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && arr[i] > arr[st.peek()]) res[st.pop()] = i;
        st.push(i);
    }
    return res;
}

4.2 逆波兰表达式求值（LeetCode 150）

public int evalRPN(String[] tokens) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String t : tokens) {
        if ("+-*/".contains(t)) {
            int b = st.pop(), a = st.pop();
            switch (t) {
                case "+" : st.push(a + b); break;
                case "-" : st.push(a - b); break;
                case "*" : st.push(a * b); break;
                case "/" : st.push(a / b); break;
            }
        } else st.push(Integer.parseInt(t));
    }
    return st.pop();
}

5. 队列 / 双端队列（滑动窗口最大值）

5.1 滑动窗口最大值（LeetCode 239）

思路：用双端队列维护当前窗口的“候选”下标（单调递减）。复杂度 O(n)。

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0) return new int[0];
    Deque<Integer> dq = new ArrayDeque<>();
    int n = nums.length;
    int[] res = new int[n - k + 1];
    for (int i = 0; i < n; i++) {
        while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) dq.pollFirst();
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
        dq.offerLast(i);
        if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

6. 堆（PriorityQueue）

6.1 合并 K 个有序链表（LeetCode 23）

思路：把每个链表头放入最小堆，循环弹出最小节点并推进。复杂度 O(N log k)。

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val);
    for (ListNode ln : lists) if (ln != null) pq.offer(ln);
    ListNode dummy = new ListNode(0), cur = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        cur.next = node; cur = cur.next;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}

6.2 数据流中位数（MedianFinder）

思路：维护两个堆（大顶堆保存较小一半，小顶堆保存较大一半）。复杂度 add O(log n)，findMedian O(1)。

class MedianFinder {
    PriorityQueue<Integer> small = new PriorityQueue<>((a,b)->b-a); // max-heap
    PriorityQueue<Integer> large = new PriorityQueue<>(); // min-heap

    public void addNum(int num) {
        small.offer(num);
        large.offer(small.poll());
        if (small.size() < large.size()) small.offer(large.poll());
    }
    public double findMedian() {
        if (small.size() > large.size()) return small.peek();
        return (small.peek() + large.peek()) / 2.0;
    }
}

7. 树高级题

7.1 二叉树序列化与反序列化（LeetCode 297）

思路：BFS（层序）用特殊符号表示 null，或用前序 + 标记 null。

// BFS 序列化
class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n == null) sb.append("#,");
            else {
                sb.append(n.val).append(",");
                q.offer(n.left); q.offer(n.right);
            }
        }
        return sb.toString();
    }
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) return null;
        String[] arr = data.split(",");
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
        q.offer(root);
        int i = 1;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (!arr[i].equals("#")) { node.left = new TreeNode(Integer.parseInt(arr[i])); q.offer(node.left); }
            i++;
            if (!arr[i].equals("#")) { node.right = new TreeNode(Integer.parseInt(arr[i])); q.offer(node.right); }
            i++;
        }
        return root;
    }
}

7.2 最近公共祖先（LCA, 二叉树，LeetCode 236）

思路：递归搜索左右子树，若左右都有非 null 返回当前结点。复杂度 O(n)。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

7.3 二叉树最大路径和（LeetCode 124）

思路：每个节点计算经过该节点的最大向下路径贡献，维护全局最大。复杂度 O(n)。

private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    dfs(root);
    return maxSum;
}
private int dfs(TreeNode node) {
    if (node == null) return 0;
    int left = Math.max(0, dfs(node.left));
    int right = Math.max(0, dfs(node.right));
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
}

8. 图（高级）

8.1 拓扑排序（Kahn 算法）

思路：入度为 0 的点入队，逐出并减小邻居入度。能检测有向无环图。复杂度 O(V+E)。

public List<Integer> topoSort(int n, List<List<Integer>> adj) {
    int[] indeg = new int[n];
    for (int u = 0; u < n; u++) for (int v : adj.get(u)) indeg[v]++;
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    List<Integer> res = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll(); res.add(u);
        for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
    }
    return res.size() == n ? res : new ArrayList<>(); // 若有环则返回空
}

8.2 Dijkstra（带优先队列的邻接表版本）

复杂度 O((V+E) log V)。

class Edge { int to, w; Edge(int t, int w){to=t;this.w=w;} }
public int[] dijkstra(int n, List<List<Edge>> graph, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;
        for (Edge e : graph.get(u)) {
            if (dist[u] + e.w < dist[e.to]) {
                dist[e.to] = dist[u] + e.w;
                pq.offer(new int[]{dist[e.to], e.to});
            }
        }
    }
    return dist;
}

8.3 Bellman-Ford（带负权检测）

复杂度 O(V*E)。

public int[] bellmanFord(int n, int src, int[][] edges) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 1; i < n; i++) { // relax n-1 times
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }
    // 检测负环
    for (int[] e : edges) {
        if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
            return null; // 存在负环
        }
    }
    return dist;
}

8.4 并查集（Union-Find）

思路：用于连通性、群组合并、Kruskal 最小生成树等。带路径压缩和按秩合并。

class UnionFind {
    int[] parent, rank;
    public UnionFind(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }
    }
}

9. 动态规划（DP）

9.1 最长递增子序列（LIS） — O(n log n)

思路：维护 tails 数组，tails[i] = 最小结尾值使得长度为 i+1。可选重建路径。复杂度 O(n log n)。

public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int i = Arrays.binarySearch(tails, 0, size, x);
        if (i < 0) i = -(i + 1);
        tails[i] = x;
        if (i == size) size++;
    }
    return size;
}

9.2 0/1 背包（经典 DP）

时间 O(nW)，空间可滚动到 O(W)。

public int knapsack(int W, int[] wt, int[] val) {
    int n = wt.length;
    int[] dp = new int[W + 1];
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= wt[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

9.3 字符串拆分（Word Break，LeetCode 139）

思路：DP，dp[i] = [0..i)是否可拆分。复杂度 O(n^2)。

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> set = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && set.contains(s.substring(j, i))) { dp[i] = true; break; }
        }
    }
    return dp[s.length()];
}

10. 回溯（Backtracking）

10.1 N 皇后（LeetCode 51）

思路：回溯 + 列 / 斜对角剪枝，可用位运算优化。

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(0, board, res, n);
    return res;
}
private void backtrack(int row, char[][] board, List<List<String>> res, int n) {
    if (row == n) {
        List<String> sol = new ArrayList<>();
        for (char[] r : board) sol.add(new String(r));
        res.add(sol);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (!isValid(board, row, col, n)) continue;
        board[row][col] = 'Q';
        backtrack(row + 1, board, res, n);
        board[row][col] = '.';
    }
}
private boolean isValid(char[][] board, int row, int col, int n) {
    for (int i = 0; i < row; i++) if (board[i][col] == 'Q') return false;
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) if (board[i][j] == 'Q') return false;
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) if (board[i][j] == 'Q') return false;
    return true;
}

10.2 组合总和（Combination Sum，LeetCode 39）

思路：回溯，注意去重与剪枝（排序后剪枝）。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> res = new ArrayList<>();
    back(candidates, 0, target, new ArrayList<>(), res);
    return res;
}
private void back(int[] cand, int idx, int target, List<Integer> path, List<List<Integer>> res) {
    if (target == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = idx; i < cand.length; i++) {
        if (cand[i] > target) break;
        path.add(cand[i]);
        back(cand, i, target - cand[i], path, res); // i 允许重复
        path.remove(path.size() - 1);
    }
}

11. 字符串算法

11.1 KMP（计算 LPS）

思路：预处理模式串得到最长相同前后缀数组 lps，然后线性匹配。复杂度 O(n+m)。

public int[] computeLPS(String pat) {
    int n = pat.length();
    int[] lps = new int[n];
    int len = 0, i = 1;
    while (i < n) {
        if (pat.charAt(i) == pat.charAt(len)) { lps[i++] = ++len; }
        else if (len > 0) len = lps[len - 1];
        else { lps[i++] = 0; }
    }
    return lps;
}
public int kmp(String s, String pat) {
    int[] lps = computeLPS(pat);
    int i = 0, j = 0;
    while (i < s.length()) {
        if (s.charAt(i) == pat.charAt(j)) { i++; j++; if (j == pat.length()) return i - j; }
        else if (j > 0) j = lps[j - 1];
        else i++;
    }
    return -1;
}

11.2 Rabin-Karp（字符串哈希）

思路：用滚动哈希快速比较子串，注意哈希冲突处理。复杂度平均 O(n).

12. 字典树 Trie

class Trie {
    private static class Node {
        Node[] next = new Node[26];
        boolean end;
    }
    private Node root = new Node();
    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
            cur = cur.next[c - 'a'];
        }
        cur.end = true;
    }
    public boolean search(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            cur = cur.next[c - 'a'];
            if (cur == null) return false;
        }
        return cur.end;
    }
    public boolean startsWith(String prefix) {
        Node cur = root;
        for (char c : prefix.toCharArray()) {
            cur = cur.next[c - 'a'];
            if (cur == null) return false;
        }
        return true;
    }
}

13. 线段树 / 树状数组（Fenwick）

13.1 树状数组（Fenwick）

功能：前缀和 / 单点更新，构建简单，复杂度 O(log n)。

class Fenwick {
    int n; int[] bit;
    public Fenwick(int n) { this.n = n; bit = new int[n + 1]; }
    public void update(int i, int delta) { for (; i <= n; i += i & -i) bit[i] += delta; }
    public int query(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
    public int rangeQuery(int l, int r) { return query(r) - query(l - 1); }
}

13.2 线段树（区间和 / 区间更新）

实现略长，模式熟悉后直接写模板即可 —— 支持区间查询/更新，复杂度 O(log n)。

14. 位运算 / 数学小技巧

单数：x & 1；取反 ~x。
异或特性：a ^ a = 0，用于求单数、交换不需要临时变量等。
lowbit(x) = x & -x（树状数组用到）。
统计 1 的个数（Hamming weight）：

public int hammingWeight(int n) {
    int cnt = 0;
    while (n != 0) { n &= (n - 1); cnt++; }
    return cnt;
}

单数问题（数组中其它数出现两次，只有一个出现一次）：使用 XOR。

public int singleNumber(int[] nums) {
    int res = 0;
    for (int x : nums) res ^= x;
    return res;
}

15. 设计题：LRU Cache（双向链表 + 哈希表）

class LRUCache {
    class Node { int key, val; Node prev, next; Node(int k,int v){key=k;val=v;} }
    private int capacity;
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(0,0), tail = new Node(0,0);
    public LRUCache(int cap) {
        capacity = cap;
        head.next = tail; tail.prev = head;
    }
    private void remove(Node node) {
        node.prev.next = node.next; node.next.prev = node.prev;
    }
    private void addToHead(Node node) {
        node.next = head.next; node.prev = head;
        head.next.prev = node; head.next = node;
    }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node); addToHead(node);
        return node.val;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key); node.val = value;
            remove(node); addToHead(node);
        } else {
            if (map.size() == capacity) {
                Node tailPrev = tail.prev;
                remove(tailPrev);
                map.remove(tailPrev.key);
            }
            Node node = new Node(key, value);
            addToHead(node); map.put(key, node);
        }
    }
}

小结与复习建议（给你一个刷题路线）

基础题（数组 / 链表 / 栈 / 队列 / 哈希表）：先熟练增删查遍历，能写模板。
递归 + 树（中序/前序/后序/层序） → 再做 LCA、序列化、最低深度。
双指针 / 滑动窗口 / 单调栈：拿来解决子数组、子串类题。
堆 / 并查集 / 图（BFS/DFS/Dijkstra/拓扑） → 面试常考。
动态规划：从经典 1D DP → 背包、序列 DP → 状态压缩。
回溯：背诵回溯模板，练 N 皇后、子集 / 组合 / 排列变体。
设计题：LRU/MedianFinder/Trie/SegmentTree 模板要熟悉。