LeetCode Hot 100 速查表

本文档汇总 LeetCode Hot 100 中的高频算法模板和关键技巧，方便快速查阅和复习。

1. 基础数据结构

链表节点定义

// 单链表节点
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

// 创建链表
ListNode createList(int[] arr) {
    if (arr == null || arr.length == 0) return null;
    ListNode head = new ListNode(arr[0]);
    ListNode curr = head;
    for (int i = 1; i < arr.length; i++) {
        curr.next = new ListNode(arr[i]);
        curr = curr.next;
    }
    return head;
}

二叉树节点定义

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

2. 双指针技巧

2.1 快慢指针

// 查找链表中点
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow 指向中点（偶数长度时指向下中点）

// 判断环形链表
ListNode slow = head, fast = head.next;
while (slow != fast) {
    if (fast == null || fast.next == null) return false;
    slow = slow.next;
    fast = fast.next.next;
}
return true;

2.2 对撞指针

// 两数之和（有序数组）
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--;
    }
}

// 容器盛水
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
    int area = Math.min(height[left], height[right]) * (right - left);
    maxArea = Math.max(maxArea, area);
    if (height[left] < height[right]) {
        left++;
    } else {
        right--;
    }
}

3. 滑动窗口

// 无重复字符的最长子串
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0, maxLen = 0;
    
    while (right < s.length()) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        right++;
        
        // 收缩窗口直到满足条件
        while (window.get(c) > 1) {
            char d = s.charAt(left);
            window.put(d, window.get(d) - 1);
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

4. 哈希表

4.1 基础使用

// HashMap
Map<Integer, Integer> map = new HashMap<>();
map.put(key, value);
map.get(key);                    // 获取值
map.getOrDefault(key, default);  // 安全获取
map.containsKey(key);            // 检查键
map.remove(key);                 // 删除

// HashSet
Set<Integer> set = new HashSet<>();
set.add(value);
set.contains(value);
set.remove(value);

4.2 两数之和模板

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

5. 二叉树遍历

5.1 前序遍历（根-左-右）

// 递归
public void preorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    result.add(root.val);
    preorder(root.left, result);
    preorder(root.right, result);
}

// 迭代
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

5.2 中序遍历（左-根-右）

// 递归
public void inorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    inorder(root.left, result);
    result.add(root.val);
    inorder(root.right, result);
}

// 迭代
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

5.3 后序遍历（左-右-根）

// 递归
public void postorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    postorder(root.left, result);
    postorder(root.right, result);
    result.add(root.val);
}

// 迭代
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) return result;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.addFirst(node.val); // 头插法
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return result;
}

5.4 层序遍历

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> level = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

6. 图论

6.1 BFS 模板

public void bfs(int[][] graph, int start) {
    boolean[] visited = new boolean[graph.length];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println(node);
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

6.2 DFS 模板

public void dfs(int[][] graph, int node, boolean[] visited) {
    visited[node] = true;
    System.out.println(node);
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

6.3 岛屿问题模板

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    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') {
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || 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);
}

7. 动态规划

7.1 一维 DP 模板

// 爬楼梯
public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 最大子数组和
public int maxSubArray(int[] nums) {
    int pre = 0, res = nums[0];
    for (int num : nums) {
        pre = Math.max(pre + num, num);
        res = Math.max(res, pre);
    }
    return res;
}

// 最长递增子序列
public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Arrays.stream(dp).max().orElse(0);
}

7.2 二维 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];
}

// 编辑距离
public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
    }
    return dp[m][n];
}

7.3 背包问题

// 0-1 背包
public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j >= weights[i - 1]) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][capacity];
}

// 一维优化
public int knapsackOptimized(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

8. 回溯算法

// 全排列
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (current.contains(nums[i])) continue;
        current.add(nums[i]);
        backtrack(result, current, nums);
        current.remove(current.size() - 1);
    }
}

// 子集
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, int start) {
    result.add(new ArrayList<>(current));
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        backtrack(result, current, nums, i + 1);
        current.remove(current.size() - 1);
    }
}

// 组合总和
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> current, int[] candidates, int target, int start) {
    if (target == 0) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = start; i < candidates.length && candidates[i] <= target; i++) {
        current.add(candidates[i]);
        backtrack(result, current, candidates, target - candidates[i], i);
        current.remove(current.size() - 1);
    }
}

9. 栈和队列

9.1 单调栈

// 每日温度（下一个更大元素）
public int[] dailyTemperatures(int[] temperatures) {
    int[] result = new int[temperatures.length];
    Stack<Integer> stack = new Stack<>();
    
    for (int i = 0; i < temperatures.length; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    return result;
}

// 柱状图中最大的矩形
public int largestRectangleArea(int[] heights) {
    int[] newHeights = new int[heights.length + 2];
    System.arraycopy(heights, 0, newHeights, 1, heights.length);
    
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    int maxArea = 0;
    
    for (int i = 1; i < newHeights.length; i++) {
        while (newHeights[i] < newHeights[stack.peek()]) {
            int height = newHeights[stack.pop()];
            int width = i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

9.2 优先级队列（堆）

// 数组中的第 K 个最大元素
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return heap.peek();
}

// 前 K 个高频元素
public List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    
    PriorityQueue<Map.Entry<Integer, Integer>> heap = 
        new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
    
    for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
        heap.offer(entry);
    }
    
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        result.add(heap.poll().getKey());
    }
    return result;
}

10. 二分查找

10.1 标准二分查找

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;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

10.2 左边界二分查找

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

10.3 右边界二分查找

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

11. 常用技巧

11.1 原地交换

// 数组中重复的数字（抽屉原理）
public List<Integer> findDuplicates(int[] nums) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        int index = Math.abs(nums[i]) - 1;
        if (nums[index] < 0) {
            result.add(Math.abs(nums[i]));
        } else {
            nums[index] = -nums[index];
        }
    }
    return result;
}

11.2 前缀和

// 和为 K 的子数组
public int subarraySum(int[] nums, int k) {
    int count = 0, preSum = 0;
    Map<Integer, Integer> prefixSum = new HashMap<>();
    prefixSum.put(0, 1);
    
    for (int num : nums) {
        preSum += num;
        if (prefixSum.containsKey(preSum - k)) {
            count += prefixSum.get(preSum - k);
        }
        prefixSum.put(preSum, prefixSum.getOrDefault(preSum, 0) + 1);
    }
    return count;
}

11.3 差分数组

// 航班预订统计
public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n];
    for (int[] booking : bookings) {
        int first = booking[0] - 1;
        int last = booking[1] - 1;
        int seats = booking[2];
        diff[first] += seats;
        if (last + 1 < n) diff[last + 1] -= seats;
    }
    
    int[] result = new int[n];
    result[0] = diff[0];
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] + diff[i];
    }
    return result;
}

12. 时间复杂度速查

算法类型	平均时间复杂度	最坏时间复杂度	空间复杂度
冒泡排序	O(n²)	O(n²)	O(1)
快速排序	O(n log n)	O(n²)	O(log n)
归并排序	O(n log n)	O(n log n)	O(n)
堆排序	O(n log n)	O(n log n)	O(1)
二分查找	O(log n)	O(log n)	O(1)
哈希查找	O(1)	O(n)	O(n)
深度优先搜索	O(V+E)	O(V+E)	O(V)
广度优先搜索	O(V+E)	O(V+E)	O(V)

13. 题目分类速查

数组类

• 最大子数组和 → 贪心/DP
• 合并区间 → 排序 + 双指针
• 轮转数组 → 三次反转
• 除自身乘积 → 前缀积

链表类

• 反转链表 → 双指针迭代
• 环形链表 → 快慢指针
• 相交链表 → 双指针
• 合并K个链表 → 堆/归并

树类

• 二叉树遍历 → 递归/迭代
• 层序遍历 → BFS
• 公共祖先 → 递归

动态规划

• 爬楼梯 → 斐波那契
• 打家劫舍 → 一维DP
• 背包问题 → 二维DP/一维优化
• 编辑距离 → 二维DP

回溯

• 全排列 → 回溯
• 子集 → 回溯
• 组合总和 → 回溯 + 剪枝

14. 常见错误汇总

1. 数组索引越界：访问数组前检查边界
2. 空指针异常：使用节点前检查是否为null
3. 无限循环：循环条件确保会终止
4. 整数溢出：使用long类型进行大数运算
5. 深拷贝遗漏：返回结果时创建新对象
6. 原地修改：需要保留原数据时先复制

---

参考资料

• LeetCode 官方
• 代码随想录
• labuladong 的算法小抄