LeetCode 热题 100 算法通关指南及代码模板

2. 双指针 (Two Pointers)

• 核心思想：通过快慢指针或左右指针缩小搜索范围，降低时间复杂度。
• 常用集合：数组、链表。
• 口诀记忆：'有序数组左右夹，原地修改快慢跑'
• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 比喻：两个人同时在跑道上跑步，速度不同或者从不同位置开始
• 心法与模板：
  • 心法：看到有序数组的配对问题，立刻想左右指针。看到需要原地修改数组或链表找环/中点，立刻想快慢指针。
    • 需要注意指针移动是否独立于循环，如果是，考虑 while 循环！
    • 对索引没有要求的，比如求和，可以考虑排序
• 模板 (快慢指针，适用于原地修改数组，如"移动零")：

public void moveZeroes(int[] nums) {
    int slow = 0; // slow 指向下一个非零元素要放置的位置
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            // 交换元素（更通用的写法）
            int temp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = temp;
            slow++;
        }
    }
}

模板 (左右指针，适用于有序数组)：

public int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            // 找到了，根据题目要求处理
            return new int[]{left, right};
        } else if (sum < target) {
            left++; // 和太小，左指针右移增大和
        } else {
            right--; // 和太大，右指针左移减小和
        }
    }
    return new int[0]; // 未找到
}

真人心得： 所谓配对，就是几个元素遵守某个规则得到预期值。而我们要做的就是找出遵守这个规则的元素。既然是与规则相关，那么将整个数组排序，有利于我们根据规则找到值。这就是用双指针解决两数之和的思路，就是一个有序数组，左右指针，然后夹逼。注意：为什么开始的两数之和使用哈希解决，因为要返回的是下标，哈希可以直接存储下标。

• 经典题目：
  • LeetCode 15: 三数之和
  • LeetCode 283: 移动零
  • LeetCode 141: 环形链表
  • LeetCode 11：盛最多水的容器

3. 滑动窗口 (Sliding Window)

• 核心思想：维护一个动态窗口，动态调整窗口大小。
• 常用集合：哈希表、数组。
• 口诀记忆：'连续子串滑窗口，左右指针配哈希'
• 时间复杂度：O(n)
• 空间复杂度：O(k)，k 是窗口内不同字符的数量
• 心法与模板：
  • 心法：题目要求"连续子数组/子串"的"最长/最短/数量"问题，99% 是滑动窗口。本质是双指针的优化。

优化模板 (无重复字符的最长子串 - 具体化版本)：

public int lengthOfLongestSubstring(String s) {
    // 1. 初始化窗口和结果
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int maxLen = 0;
    // 2. 右指针扩大窗口
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 3. 具体的收缩条件：当窗口中有重复字符时
        while (window.get(c) > 1) {
            char d = s.charAt(left);
            left++;
            window.put(d, window.get(d) - 1);
        }
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

• 经典题目：
  • LeetCode 3: 无重复字符的最长子串
  • LeetCode 76: 最小覆盖子串
  • LeetCode 438: 找到字符串中所有字母异位词

4. 子串 (Substring)

• 核心思想：滑动窗口（连续子串）、前缀和 + 哈希表（子数组和）。
• 常用集合：哈希表、单调队列。
• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 心法与模板：
  • 心法：如果题目和"子数组的和"有关，立刻想"前缀和 + 哈希表"。preSum[j] - preSum[i] = k 这个公式是解题关键。

模板 (前缀和 + 哈希表，求和为 K 的子数组)：

public int subarraySum(int[] nums, int k) {
    // 1. 初始化哈希表（记录每种前缀和出现的次数）
    Map<Integer, Integer> map = new HashMap<>();
    // 重要：初始化前缀和为 0 的出现 1 次
    map.put(0, 1);
    int preSum = 0;
    int count = 0;
    // 2. 遍历数组
    for (int num : nums) {
        preSum += num;
        // 3. 关键：查找符合条件的前缀和
        if (map.containsKey(preSum - k)) {
            count += map.get(preSum - k);
        }
        // 4. 将当前前缀和存入哈希表
        map.put(preSum, map.getOrDefault(preSum, 0) + 1);
    }
    return count;
}

• 经典题目：
  • LeetCode 560: 和为 K 的子数组
  • LeetCode 53: 最大子数组和
  • LeetCode 209: 长度最小的子数组

5. 普通数组 (Array)

• 核心思想：贪心、排序、双指针、数学推导，动态规划。
• 常用集合：数组（原地修改）。
• 心法与模板：
  • 心法：当题目要求 O(1) 空间复杂度，且数组元素范围在 [1, N] 之间时，可以把数组本身当作哈希表，利用正负号或交换元素到对应索引位置来标记信息。这叫"原地哈希"。
• 经典题目：
  • LeetCode 41: 缺失的第一个正数
  • LeetCode 442: 数组中重复的数据
  • LeetCode 287: 寻找重复数
  • LeetCode 53: 最大子数组和
  • LeetCode 56：合并区间
  • LeetCode 189：轮转数组

模板 (原地哈希，找缺失的第一个正数)：

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    // 1. 将所有数字放到它应该在的位置上
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    // 2. 再次遍历，找到第一个不在正确位置上的数字
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

6. 矩阵 (Matrix)

• 核心思想：模拟、哈希表标记、双指针。
• 常用集合：二维数组。
• 时间复杂度：O(m*n)
• 空间复杂度：通常是 O(1)
• 心法与模板：
  • 心法：处理矩阵问题，关键是控制好边界和方向。对于旋转、螺旋等问题，可以一层一层地处理。
• 经典题目：
  • LeetCode 54: 螺旋矩阵
  • LeetCode 48: 旋转图像
  • LeetCode 73: 矩阵置零
  • LeetCode 240：搜索二维矩阵 II

模板 (螺旋矩阵)：

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix == null || matrix.length == 0) return result;
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (int i = left; i <= right; i++) result.add(matrix[top][i]);
        top++;
        for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
        right--;
        if (top <= bottom) {
            for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
            left++;
        }
    }
    return result;
}

7. 链表 (Linked List)

• 核心思想：指针操作、递归、哈希表辅助。
• 口诀记忆：'虚拟头节点是神器，快慢指针找环中'
• 时间复杂度：通常是 O(n)
• 空间复杂度：通常是 O(1)
• 心法与模板：
  • 心法：链表题目的精髓在于指针操作。为了防止指针丢失，经常需要一个 prev 指针来保存前一个节点。对于复杂操作，引入一个虚拟头节点(dummy head) 可以极大地简化边界条件处理。
• 经典题目：
  • LeetCode 206: 反转链表
  • LeetCode 141: 环形链表
  • LeetCode 142: 环形链表 II
  • LeetCode 21: 合并两个有序链表
  • LeetCode 234：回文链表
  • LeetCode 2：两数相加
  • LeetCode 19: 删除链表的倒数第 N 个节点
  • LeetCode 24：两两交换链表中的节点
  • LeetCode 25：K 个一组翻转链表
  • LeetCode 138：复制带随机指针的链表
  • LeetCode 148：排序链表
  • LeetCode 23：合并 K 个升序链表
  • LeetCode 146：LRU 缓存机制

万能模板 (虚拟头节点版本)：

public ListNode universalTemplate(ListNode head) {
    // 1. 创建虚拟头节点，简化边界处理
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    // 2. 定义工作指针
    ListNode prev = dummy;
    ListNode curr = head;
    // 3. 遍历处理
    while (curr != null) {
        // ... 根据具体题目处理 curr 节点 ...
        // 标准前进步骤
        prev = curr;
        curr = curr.next;
    }
    // 4. 返回新的头节点
    return dummy.next;
}

模板 (反转链表)：

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

8. 二叉树 (Binary Tree)

• 核心思想：递归、迭代（栈/队列）、分治、BFS/DFS。
• 时间复杂度：通常是 O(n)
• 空间复杂度：递归 O(h)
• 心法与模板：
  • 心法：90% 的二叉树问题都可以用递归解决。写递归代码，只需要思考三件事：终止条件、当前层做什么、递归调用。
• 经典题目：
  • LeetCode 104: 二叉树的最大深度
  • LeetCode 94: 二叉树的中序遍历
  • LeetCode 226：翻转二叉树
  • LeetCode 543：二叉树的直径
  • LeetCode 102：二叉树的层序遍历
  • LeetCode 108：将有序数组转换为二叉搜索树
  • LeetCode 98：验证二叉搜索树
  • LeetCode 230: 二叉搜索树中第 K 小的元素
  • LeetCode 199：二叉树的右视图
  • LeetCode 114: 二叉树展开为链表
  • LeetCode 105：从前序与中序遍历序列构造二叉树
  • LeetCode 437：路径总和 III
  • LeetCode 236：二叉树的最近公共祖先
  • LeetCode 124 :二叉树中的最大路径和

模板 (层序遍历 - BFS)：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(currentLevel);
    }
    return result;
}

模板 (递归遍历)：

void traverse(TreeNode root) {
    if (root == null) return;
    // 前序位置
    System.out.println(root.val);
    traverse(root.left);
    // 后序位置
    traverse(root.right);
}

9. 图论 (Graph)

• 核心思想：DFS/BFS、拓扑排序、Trie 树，并查集。
• 时间复杂度：通常是 O(V+E)
• 空间复杂度：通常是 O(V+E)
• 心法与模板：
  • 心法：图论问题第一步是建图（通常用邻接表）。然后根据问题选择遍历方式：求最短路径用 BFS，求连通性/所有路径用 DFS。
• 经典题目：
  • LeetCode 200: 岛屿数量
  • LeetCode 207: 课程表
  • LeetCode 133: 克隆图
  • LeetCode 994: 腐烂的橘子
  • LeetCode 208: 实现 Trie (前缀树)

模板 (DFS 遍历图，课程表问题)：

class Solution {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) edges.add(new ArrayList<>());
        for (int[] info : prerequisites) edges.get(info[1]).add(info[0]);
        visited = new int[numCourses];
        for (int i = 0; i < edges.size() && valid; i++) {
            if (visited[i] == 0) dfs(i);
        }
        return valid;
    }

    private void dfs(int i) {
        if (visited[i] == 1) { valid = false; return; }
        if (visited[i] == 2) return;
        visited[i] = 1;
        for (int node : edges.get(i)) dfs(node);
        visited[i] = 2;
    }
}

模板 (BFS 遍历图)：

public int bfs(int start, int target, Map<Integer, List<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    queue.offer(start);
    visited.add(start);
    int steps = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int node = queue.poll();
            if (node == target) return steps;
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        steps++;
    }
    return -1;
}

10. 回溯 (Backtracking)

• 核心思想：递归 + 剪枝（'做选择，撤销选择'）。
• 时间复杂度：O(n!) 或 O(2^n)
• 空间复杂度：O(n)
• 心法与模板：
  • 心法：回溯是"暴力枚举"的优雅版，适用于所有"组合、排列、子集、棋盘"问题。记住**'路径、选择列表、结束条件'**三要素。
• 经典题目：
  • LeetCode 46: 全排列
  • LeetCode 78: 子集
  • LeetCode 17: 电话号码的字母组合
  • LeetCode 22: 括号生成
  • LeetCode 79: 单词搜索
  • LeetCode 131 分割回文串
  • LeetCode 51 N 皇后

模板 (通用)：

List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;

void backtrack(int[] nums, int startIndex) {
    // 1. 终止条件
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 2. 遍历选择列表
    for (int i = startIndex; i < nums.length; i++) {
        if (used[i]) continue;
        // 3. 做选择
        path.add(nums[i]);
        used[i] = true;
        // 4. 进入下一层决策树
        backtrack(nums, i + 1);
        // 5. 撤销选择
        path.removeLast();
        used[i] = false;
    }
}

11. 二分查找 (Binary Search)

• 核心思想：利用数组有序性，通过二分缩小搜索范围。
• 时间复杂度：O(log n)
• 空间复杂度：O(1)
• 心法与模板：
  • 心法：只要看到"有序数组"中的"查找"问题，就用二分法。关键在于循环条件 (left <= right) 和边界收缩 (left = mid + 1 或 right = mid - 1)。

模板 (左边界搜索)：

public int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] != target) return -1;
    return left;
}

模板 (标准二分查找)：

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (target > nums[mid]) left = mid + 1;
        if (target < nums[mid]) right = mid - 1;
    }
    return -1;
}

• 经典题目：
  • LeetCode 153：寻找旋转排序数组中的最小值
  • LeetCode 34: 在排序数组中查找元素的第一个和最后一个位置
  • LeetCode 74: 搜索二维矩阵
  • LeetCode 35: 搜索插入位置
  • LeetCode 33：搜索旋转排序数组

12. 栈 (Stack)

• 核心思想：利用 LIFO 特性（匹配、解码），或维护单调性（单调栈）。
• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 心法与模板：
  • 心法：遇到"括号匹配"、"消除相邻重复项"等具有"最近相关性"的问题，用普通栈。遇到"寻找下一个更大/更小元素"的问题，用单调栈。
• 经典题目：
  • LeetCode 20: 有效的括号
  • LeetCode 155 最小栈
  • LeetCode 394：字符串解码
  • LeetCode 739：每日温度

模板 (括号匹配)：

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

模板 (单调栈，找下一个更大元素)：

public int[] nextGreaterElement(int[] nums) {
    int[] result = new int[nums.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int prevIndex = stack.pop();
            result[prevIndex] = nums[i];
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        result[stack.pop()] = -1;
    }
    return result;
}

13. 堆 (Heap)

• 核心思想：利用优先级特性处理 Top K 问题、中位数问题。
• 常用集合：优先队列 (PriorityQueue)。
• 时间复杂度：插入 O(log n)，取顶 O(1)
• 空间复杂度：O(n)
• 心法与模板：
  • 心法：看到"Top K"或"第 K 大/小"的问题，立刻想堆。求 Top K 大，用小顶堆；求 Top K 小，用大顶堆。
• 经典题目：
  • LeetCode 215: 数组中的第 K 个最大元素
  • LeetCode 347: 前 K 个高频元素
  • LeetCode 295: 数据流的中位数

模板 (数据流中位数 - 双堆)：

class MedianFinder {
    PriorityQueue<Integer> maxHeap; // 左半部分，大顶堆
    PriorityQueue<Integer> minHeap; // 右半部分，小顶堆

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}

模板 (求 Top K 大元素)：

public List<Integer> topKLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int num : nums) {
        if (minHeap.size() < k) {
            minHeap.offer(num);
        } else if (num > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(num);
        }
    }
    return new ArrayList<>(minHeap);
}

14. 贪心算法 (Greedy)

• 核心思想：局部最优 → 全局最优。
• 时间复杂度：通常是 O(n) 或 O(nlogn)
• 空间复杂度：通常是 O(1) 或 O(n)
• 心法与模板：
  • 心法：贪心没有固定模板，关键是找到贪心策略。通常需要排序来辅助决策。
• 经典题目：
  • LeetCode 121：买卖股票的最佳时机
  • LeetCode 55：跳跃游戏
  • LeetCode 45：跳跃游戏 II
  • LeetCode 763: 划分字母区间

编码实现：

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int count = 1;
    int end = intervals[0][1];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }
    return intervals.length - count;
}

15 & 16. 动态规划 (DP)

• 核心思想：状态转移，保存子问题结果。
• 时间复杂度：通常是 O(n^2) 或 O(n*m)
• 空间复杂度：通常是 O(n) 或 O(n*m)
• 心法与模板：
  • 心法：DP 是硬骨头，但有套路。记住**"DP 五步曲"**：定义 dp 数组含义、找出状态转移方程、初始化 dp 数组、确定遍历顺序、返回最终结果。

模板 (一维 DP，以"完全平方数"为例)：

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) {
            int square = i * i;
            for (int j = square; j <= n; j++) {
                if (dp[j - square] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - square] + 1);
                }
            }
        }
        return dp[n];
    }
}

模板 (单词拆分为例)：

public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    Set<String> wordSet = new HashSet<>(wordDict);
    for (int i = 1; i <= n; i++) {
        for (String word : wordSet) {
            int wordLen = word.length();
            if (wordLen <= i && dp[i - wordLen] && s.substring(i - wordLen, i).equals(word)) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

模板 (二维 DP，以"不同路径"为例)：

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

• 经典题目：
  • LeetCode 70: 爬楼梯
  • LeetCode 118：杨辉三角
  • LeetCode 198：打家劫舍
  • LeetCode 279：完全平方数
  • LeetCode 322: 零钱兑换
  • LeetCode 139：单词拆分
  • LeetCode 300：最长递增子序列
  • LeetCode 152：乘积最大子数组
  • LeetCode 416: 分割等和子集
  • LeetCode 32: 最长有效括号
  • LeetCode 62：不同路径
  • LeetCode 64：最小路径和
  • LeetCode 5：最长回文子串
  • LeetCode 1143：最长公共子序列
  • LeetCode 72：编辑距离

17. 技巧 (Tricks)

• 核心思想：位运算、摩尔投票、双指针、数学规律。
• 时间复杂度：通常是 O(n)
• 空间复杂度：通常是 O(1)
• 心法与模板：
  • 心法：这些是"神来之笔"，需要专门记忆。位运算的异或 (XOR) 特别好用：a ^ a = 0, a ^ 0 = a。
• 经典题目：
  • LeetCode 136: 只出现一次的数字
  • LeetCode 169: 多数元素
  • LeetCode 75: 颜色分类
  • LeetCode 31: 下一个排列
  • LeetCode 287: 寻找重复数

模板 (摩尔投票，找众数)：

public int majorityElement(int[] nums) {
    int candidate = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (count == 0) {
            candidate = nums[i];
            count = 1;
        } else if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

模板 (位运算，找只出现一次的数字)：

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

18. 字符串算法 (String)

• 核心思想：哈希表、滑动窗口、字符串匹配算法
• 时间复杂度：KMP O(m+n)
• 空间复杂度：通常是 O(n)
• 心法与模板：
  • 心法：字符串处理问题通常涉及模式匹配、统计或转换。对于匹配问题，如果是简单匹配用 indexOf()，复杂匹配考虑 KMP 算法。
• 经典题目：
  • LeetCode 208: 实现 Trie (前缀树)
  • LeetCode 28: 实现 strStr()
  • LeetCode 14: 最长公共前缀

模板 (KMP 算法)：

public int strStr(String haystack, String needle) {
    if (needle.length() == 0) return 0;
    int[] next = new int[needle.length()];
    for (int i = 1, j = 0; i < needle.length(); i++) {
        while (j > 0 && needle.charAt(i) != needle.charAt(j)) j = next[j - 1];
        if (needle.charAt(i) == needle.charAt(j)) j++;
        next[i] = j;
    }
    for (int i = 0, j = 0; i < haystack.length(); i++) {
        while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = next[j - 1];
        if (haystack.charAt(i) == needle.charAt(j)) j++;
        if (j == needle.length()) return i - needle.length() + 1;
    }
    return -1;
}

模板 (Trie 树)：

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode();
            node = node.children[c - 'a'];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.children[c - 'a'] == null) return null;
            node = node.children[c - 'a'];
        }
        return node;
    }

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
    }
}

19. 并查集 (Union Find)

• 核心思想：高效处理元素分组和合并
• 时间复杂度：几乎 O(1)
• 空间复杂度：O(n)
• 心法与模板：
  • 心法：并查集适用于动态连通性问题。当需要频繁判断两个元素是否连通，或者合并两个连通分量时，并查集可以做到近乎常数时间复杂度。
• 经典题目：
  • LeetCode 200: 岛屿数量
  • LeetCode 547: 省份数量
  • LeetCode 684: 冗余连接

模板：

class UnionFind {
    private int[] parent;
    private int[] rank;
    private int count;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = 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 rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else { parent[rootY] = rootX; rank[rootX]++; }
            count--;
        }
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int getCount() {
        return count;
    }
}

学习路线图

按照以下顺序学习算法，可以从易到难循序渐进：

第一阶段：基础算法与数据结构

1. 哈希表 - 简单直观，解决查找问题
2. 数组与双指针 - 处理有序数据，解决配对问题
3. 栈与队列 - 处理先进后出和先进先出问题
4. 二分查找 - 学习如何高效查找

第二阶段：链表与树

5. 链表 - 掌握指针操作
6. 二叉树 - 学习树的递归遍历
7. 堆 - Top K 问题的解决方案

第三阶段：进阶数据结构

8. 滑动窗口 - 处理子串问题
9. 单调栈/队列 - 解决"下一个更大"类问题
10. 并查集 - 解决图的连通性问题

第四阶段：进阶算法

11. 回溯算法 - 组合/排列/子集问题
12. 贪心算法 - 局部最优解问题
13. 动态规划 (基础) - 重叠子问题

第五阶段：高级算法

14. 图论算法 - DFS、BFS、拓扑排序
15. 高级动态规划 - 编辑距离、区间 DP 等
16. 字符串算法 - KMP、Trie 树
17. 位运算与数学技巧 - 解决特殊问题

快速学习加速技巧

口诀记忆总结

• 哈希表：'一看配对就哈希，空间换时间是王道'
• 双指针：'有序数组左右夹，原地修改快慢跑'
• 滑动窗口：'连续子串滑窗口，左右指针配哈希'
• 链表：'虚拟头节点是神器，快慢指针找环中'
• 二叉树：'递归三问终止条件，当前处理递归调用'
• 回溯：'路径选择终止条件，做选择递归撤选择'
• 动态规划：'定义状态找转移，初始边界看遍历'
• 二分查找：'左右指针中间点，相等返回小则左'

30 秒快速识别表