核心思想：如何有效刷 LeetCode？

在看具体题解之前,建立正确的刷题方法论至关重要。

1. 先思考，再编码：拿到题目后，先自己思考可能的解法，比如暴力法、优化思路等，不要急着看题解。
2. 由浅入深：先尝试用自己最熟悉的方法（如暴力法）解决，确保能通过，然后再思考如何优化时间或空间复杂度。
3. 理解题解，而非背诵：阅读优质题解时，重点理解其思路、数据结构选择的原因以及代码实现的巧妙之处，然后合上题解，自己重新实现一遍。
4. 举一反三：解完一道题后，思考它的变体、相关题型以及可以使用的通用模板或思想（如双指针、滑动窗口、回溯等）。
5. 定期复盘：使用 LeetCode 的“标签”功能，对同类型的题目进行归类复习，巩固解题套路。

Java 解题常用数据结构与技巧

掌握这些是写出高效 Java 代码的基础。

基础数据结构

• Arrays 和 ArrayList：
  • Arrays.asList()：快速创建一个 List，但要注意它返回的是固定长度的列表。
  • ArrayList：动态数组，增删改查的时间复杂度需要了解。
• HashMap 和 HashSet：
  • 哈希表的基石，用于快速查找、去重、建立映射关系。
  • 核心方法：put(), get(), containsKey(), keySet(), values()。
  • 常见场景：两数和、频率统计、替代数组索引等。
• LinkedList：
  • 双向链表,在头尾频繁插入删除时性能优于 ArrayList。
• Stack：

  后进先出,用于括号匹配、表达式求值、递归转非递归等。

• Queue 和 LinkedList / PriorityQueue：
  • LinkedList 可作为 Queue 使用。
  • PriorityQueue：优先队列，底层是堆，用于实现 Top K 问题、Dijkstra 算法等。
• String 和 StringBuilder：
  • String 是不可变的，频繁修改应使用 StringBuilder 提高性能。
• TreeMap 和 TreeSet：

  基于红黑树,可以自动对键进行排序，用于需要有序的场景。

核心算法思想

• 双指针
  • 快慢指针：判断链表环、寻找链表中点。
  • 左右指针：二分查找、反转数组/字符串、三数之和。
  • 滑动窗口：解决子数组/子串问题，如最小覆盖子串、无重复字符的最长子串。
• 排序
  • Arrays.sort()：对基本类型和对象数组排序，对象数组需要实现 Comparable 接口或提供 Comparator。
  • 排序后双指针：是很多问题的预处理步骤。
• 二分查找
  • 不仅用于有序数组,也可用于在单调性问题上查找边界。
  • Java 实现：注意 left, right, mid 的边界条件，以及 while 循环的判断条件 (left < right vs left <= right)。
• 递归与回溯
  • 递归：用于解决具有自相似结构的问题，如树/图的遍历、分治。
  • 回溯：递归的一种，常用于解决排列、组合、子集、棋盘等问题，核心是“做选择 -> 递归 -> 撤销选择”。
• BFS 和 DFS
  • BFS (广度优先搜索)：使用队列，通常用于寻找最短路径（无权图）、按层遍历。
  • DFS (深度优先搜索)：使用栈或递归，用于遍历、寻找路径、检测环。
• 动态规划
  • 核心：定义状态，找到状态转移方程。
  • 技巧：从暴力递归入手，发现重复子问题，然后加备忘录（自顶向下）或改用循环（自底向上）进行优化。
• 贪心算法

  每一步都做出当前看起来最优的选择,期望最终得到全局最优解，需要证明贪心策略的正确性。

  
  （图片来源网络，侵删）

Java 题解资源推荐

以下资源各有侧重,建议结合使用。

官方与社区

• LeetCode 官方题解
  • 优点：官方提供，思路清晰，代码规范，通常会给出多种解法。
  • 缺点：部分题解可能不够深入。
  • 网址：在每道题的 "Solutions" 标签页下。
• LeetCode Discuss
  • 优点：全球最大的程序员社区之一，可以找到各种奇思妙想和高质量讨论，很多“题解”其实是在评论区。
  • 缺点：信息庞杂，需要花时间甄别。
  • 网址：在每道题的 "Discuss" 标签页下。

国内优秀题解网站/博客

• 《剑指 Offer》与 LeetCode 题解 (Krahets)
  • 强烈推荐，这是 GitHub 上的一个开源项目，由 @doocs 维护。
  • 优点：
    • 极其全面：覆盖了 LeetCode 上几乎所有题目，包括《剑指 Offer》和《程序员面试金典》。
    • 质量极高：每种题目都提供多种解法（暴力、优化、最优），并配有详细的思路图解和复杂度分析。
    • 代码规范：Java 代码风格非常好，注释清晰。
    • 持续更新：紧跟 LeetCode 更新。
• 《算法第四版》配套网站 (Algs4)
  • 优点：经典算法教材，网站提供了所有算法的 Java 实现，代码规范，思想深刻，适合系统学习数据结构和算法。
• 代码随想录 (Carl)
  • 优点：以“数据结构+算法”为主线，讲解非常细致，配有大量图解，非常适合初学者建立知识体系，题目也覆盖很广。

GitHub 仓库

• LeetCode-Top
  • 优点：收录了 LeetCode 高频面试题，题目精选，质量很高，同样提供多种语言的题解。
• LeetCode-Solution
  • 优点：由知名博主 GrandYang 维护，题解非常经典，思路清晰，是很多人的启蒙资料，虽然主要是 C++，但思路可以借鉴。

Java 题解示例

为了让你更直观地感受,我们来看一道经典题：两数之和 (Two Sum)。 描述 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

暴力法 - 暴力枚举

• 思路：最直观的想法，用两层循环，遍历所有可能的两个数组合，检查它们的和是否等于 target。
• 复杂度：
  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
• Java 代码：

  class Solution {
      public int[] twoSum(int[] nums, int target) {
          int n = nums.length;
          for (int i = 0; i < n; ++i) {
              for (int j = i + 1; j < n; ++j) {
                  if (nums[i] + nums[j] == target) {
                      return new int[]{i, j};
                  }
              }
          }
          // 根据题目描述，假设有唯一解，所以这里不会执行
          return new int[0];
      }
  }

哈希表 - 一次哈希

• 思路：为了优化时间，我们需要一个能在 O(1) 时间内根据值找到其索引的数据结构，哈希表（HashMap）完美符合这个需求。

  • 我们遍历数组,对于每个元素 nums[i]，我们计算 complement = target - nums[i]。
  • 我们检查 HashMap 中是否已经存在 complement。
    • 如果存在,说明我们已经找到了两个数，它们的和是 target，直接返回它们的索引。
    • 如果不存在,我们将当前元素 nums[i] 和它的索引 i 存入 HashMap，供后续查找。

• 复杂度：

  
  （图片来源网络，侵删）
  • 时间复杂度：O(n)，我们只遍历了包含 n 个元素的列表一次，在哈希表中进行的每次查找只花费 O(1) 的时间。
  • 空间复杂度：O(n)，最坏情况下，我们需要存储 n 个键值对。

• Java 代码：

  import java.util.HashMap;
  import java.util.Map;
  class Solution {
      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];
      }
  }

代码分析：

• Map<Integer, Integer> map = new HashMap<>();：创建一个 HashMap，键是数组中的值，值是该值对应的索引。
• map.containsKey(complement)：核心操作，检查 complement 这个键是否在 map 中。
• map.get(complement)：complement 存在，获取它对应的索引（也就是之前那个数的索引）。
• map.put(nums[i], i);：将当前遍历到的数和它的索引存入 map，为后续的查找做准备。

这个例子清晰地展示了如何通过选择合适的数据结构（HashMap）将一个 O(n²) 的暴力解法优化到 O(n) 的高效解法，这也是 LeetCode 解题的核心思路之一。

学习 LeetCode Java 题解是一个循序渐进的过程：

1. 打好基础：熟练掌握 Java 常用数据 API。
2. 学习思想：理解各种算法的核心思想和适用场景。
3. 模仿实践：阅读优质题解，理解后自己动手实现。
4. 总结归纳：建立自己的题解库和知识体系。

祝你刷题愉快,早日成为算法大神！