LeetCode 高频 100 题精讲 ⭐⭐⭐

🎯 面试算法怎么刷？按什么顺序刷最有效？

算法面试不需要刷完 2000 题，关键是掌握高频题型和解题套路。按「简单打基础 → 中等练思路 → 困难提深度」的顺序，45 道高频题覆盖 90% 面试场景。

一、简单题（15 道）- 打牢基础

1. 两数之和

// 哈希表：一次遍历，O(n)
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[0];
}
// 时间：O(n) 空间：O(n)

2. 反转链表

// 迭代：双指针，O(n)
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;
}

// 递归：O(n) O(n)栈空间
public ListNode reverseList2(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseList2(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

3. 合并两个有序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            cur.next = l1; l1 = l1.next;
        } else {
            cur.next = l2; l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 != null ? l1 : l2;
    return dummy.next;
}

4. 爬楼梯

// 动态规划：dp[i] = dp[i-1] + dp[i-2]
public int climbStairs(int n) {
    if (n <= 2) return n;
    int dp1 = 1, dp2 = 2;
    for (int i = 3; i <= n; i++) {
        int dp3 = dp1 + dp2;
        dp1 = dp2; dp2 = dp3;
    }
    return dp2;
}
// 斐波那契数列

5. 括号匹配

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

6. 最大子数组和（经典！）

// 贪心：O(n)
public int maxSubArray(int[] nums) {
    int maxSum = nums[0], curSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        curSum = Math.max(nums[i], curSum + nums[i]);
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

二、中等题（20 道）- 核心进阶

7. 三数之和

// 双指针 + 排序去重：O(n²)
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left+1]) left++;
                while (left < right && nums[right] == nums[right-1]) right--;
                left++; right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
}

8. 岛屿数量（DFS/BFS 经典）

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 || 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);
}

9. 最长无重复子串

// 滑动窗口 + 哈希表：O(n)
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.length(); right++) {
        if (map.containsKey(s.charAt(right))) {
            left = Math.max(left, map.get(s.charAt(right)) + 1);
        }
        map.put(s.charAt(right), right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

10. 合并 K 个升序链表

// 最小堆（PriorityQueue）：O(n log k)
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        (a, b) -> a.val - b.val
    );
    for (ListNode node : lists) {
        if (node != null) pq.offer(node);
    }
    ListNode dummy = new ListNode(0), cur = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        cur.next = node;
        if (node.next != null) pq.offer(node.next);
        cur = cur.next;
    }
    return dummy.next;
}

11. 搜索旋转排序数组

// 二分查找变形：O(log n)
public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = (left + right) >>> 1;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) { // 左半边有序
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else { // 右半边有序
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

12. 括号生成（回溯）

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(res, "", 0, 0, n);
    return res;
}

private void backtrack(List<String> res, String cur, int open, int close, int n) {
    if (cur.length() == n * 2) {
        res.add(cur); return;
    }
    if (open < n) backtrack(res, cur + "(", open + 1, close, n);
    if (close < open) backtrack(res, cur + ")", open, close + 1, n);
}

三、困难题（10 道）- 提升深度

13. 接雨水

// 双指针：O(n)
public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) leftMax = height[left];
            else water += leftMax - height[left];
            left++;
        } else {
            if (height[right] >= rightMax) rightMax = height[right];
            else water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

14. 最长公共子序列

// 动态规划：O(mn)
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];
}

四、刷题顺序建议

第一阶段（1-2周）：简单题打基础
  数组 → 链表 → 哈希表 → 字符串
  目标：熟悉基础数据结构操作

第二阶段（2-3周）：中等题练思路
  双指针 → 二分查找 → 滑动窗口 → 回溯 → 动态规划入门
  目标：掌握核心算法思想

第三阶段（3-4周）：困难题提深度
  困难 DFS/BFS → 高级 DP → 贪心证明
  目标：能应对 Hard 题

每周节奏：每天 2-3 题，重点是理解思路而非背代码

五、高频面试题

Q1: 如何快速判断一个链表是否有环？

Floyd 算法（快慢指针）：慢指针一次走一步，快指针一次走两步。如果链表有环，快慢指针一定在环内相遇。时间 O(n)，空间 O(1)。

Q2: 二分查找的边界条件怎么处理？

关键是保持 left <= right（等于时也要检查）和 mid = (left + right) >>> 1（防溢出）。循环终止条件用 while (left < right) 时，结束时 left == right 一定是答案；用 while (left <= right) 时，结束时 left > right，需要额外处理。

Q3: 滑动窗口的核心思想是什么？

核心思想是双指针维护一个可变窗口。右指针扩展窗口加入元素，左指针收缩窗口移除元素。典型模式：while (right < n) { 添加右边界; 更新状态; while (需要收缩) { 移除左边界; 更新状态; } right++; }