• 中文 • Jackey

Java 数据结构速查手册 - LeetCode 刷题必备完整指南

掌握编程面试必备的 Java 数据结构，全面覆盖 Queue、Stack、List、Set、Map、Heap、String 和 Array 工具类。包含方法签名、时间复杂度和 LeetCode 解题模式，来自 11 年 FAANG 资深工程师。

#java #data-structures #leetcode #interview-prep #cheat-sheet #reference-guide #algorithm

引言：你的面试瑞士军刀

在用 Java 解 LeetCode 题目时，知道使用哪种数据结构以及有哪些方法可用，可能决定着你是快速解决问题还是卡壳 30 分钟。

这份指南是你刷题和面试中最常用的 Java 数据结构的速查手册。经过我在 Microsoft、Booking.com 和 Alibaba 11+ 年的经验积累，我提炼出了你会反复使用的核心操作。

如何使用本指南

  • 准备阶段：通读各个章节，熟悉可用的方法
  • 刷题阶段：将本指南作为快速查询参考
  • 面试前：复习时间复杂度表格，避免性能陷阱

Java 版本说明

  • 本指南涵盖 Java 8+ 特性
  • 所有代码示例都是面试就绪的（无外部依赖）
  • 专注于 java.util.* 包（标准库）

1. Queue 和 Stack 操作

ArrayDeque（推荐用于栈和队列）

ArrayDeque 是实现队列和栈操作的现代首选。它比 LinkedList 和 Stack 更快。

作为队列使用（FIFO）

Deque<Integer> queue = new ArrayDeque<>();

// 添加元素（队尾）
queue.offer(1);        // 返回 boolean，O(1)
queue.add(2);          // 失败时抛出异常，O(1)

// 移除元素（队首）
Integer val = queue.poll();  // 空时返回 null，O(1)
Integer val = queue.remove(); // 空时抛出异常，O(1)

// 查看（不移除）
Integer val = queue.peek();  // 空时返回 null，O(1)
Integer val = queue.element(); // 空时抛出异常，O(1)

// 大小
int size = queue.size();     // O(1)
boolean empty = queue.isEmpty(); // O(1)

作为栈使用（LIFO）

Deque<Integer> stack = new ArrayDeque<>();

// 压入（添加到栈顶）
stack.push(1);         // O(1)

// 弹出（从栈顶移除）
Integer val = stack.pop();   // 空时抛出异常，O(1)

// 查看（不移除）
Integer val = stack.peek();  // 空时返回 null，O(1)

// 大小
int size = stack.size();     // O(1)
boolean empty = stack.isEmpty(); // O(1)

作为双端队列使用（Deque）

Deque<Integer> deque = new ArrayDeque<>();

// 添加到前端
deque.offerFirst(1);   // O(1)
deque.addFirst(2);     // O(1)

// 添加到后端
deque.offerLast(3);    // O(1)
deque.addLast(4);      // O(1)

// 从前端移除
Integer val = deque.pollFirst();  // O(1)
Integer val = deque.removeFirst(); // O(1)

// 从后端移除
Integer val = deque.pollLast();   // O(1)
Integer val = deque.removeLast();  // O(1)

// 查看
Integer front = deque.peekFirst(); // O(1)
Integer back = deque.peekLast();   // O(1)

Stack（遗留类 - 面试中避免使用）

Stack<Integer> stack = new Stack<>();

stack.push(1);         // O(1)
Integer val = stack.pop();   // O(1)
Integer val = stack.peek();  // O(1)
boolean empty = stack.empty(); // O(1)
int pos = stack.search(1);   // O(n)，返回基于 1 的位置

⚠️ 面试提示：优先使用 ArrayDeque 而不是 Stack。面试官可能会指出 Stack 是遗留代码。

对比表

操作ArrayDeque (Queue)ArrayDeque (Stack)LinkedListStack (遗留)
Add/Pushoffer() O(1)push() O(1)offer() O(1)push() O(1)
Remove/Poppoll() O(1)pop() O(1)poll() O(1)pop() O(1)
Peekpeek() O(1)peek() O(1)peek() O(1)peek() O(1)
速度⚡ 最快⚡ 最快较慢较慢

常见 LeetCode 模式

单调栈：跟踪下一个更大/更小元素

Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        int idx = stack.pop();
        // 处理...
    }
    stack.push(i);
}

滑动窗口最大值：使用双端队列维护窗口内最大值

Deque<Integer> deque = new ArrayDeque<>(); // 存储索引

2. List 操作

ArrayList（动态数组）

适用于随机访问和顺序迭代。

List<Integer> list = new ArrayList<>();

// 添加元素
list.add(1);           // 添加到末尾，O(1) 摊销
list.add(0, 10);       // 在索引处插入，O(n)

// 访问元素
int val = list.get(0); // O(1)
list.set(0, 20);       // O(1)

// 移除元素
list.remove(0);        // 按索引移除，O(n)
list.remove(Integer.valueOf(10)); // 按值移除，O(n)

// 查找
boolean exists = list.contains(10); // O(n)
int index = list.indexOf(10);       // O(n)，未找到返回 -1
int lastIdx = list.lastIndexOf(10); // O(n)

// 大小
int size = list.size();      // O(1)
boolean empty = list.isEmpty(); // O(1)
list.clear();                // O(n)

// 排序
Collections.sort(list);      // O(n log n)
Collections.sort(list, Collections.reverseOrder()); // 降序

// 转换
int[] arr = list.stream().mapToInt(i -> i).toArray(); // 转为数组

LinkedList（双向链表）

适用于频繁在两端插入/删除。

LinkedList<Integer> list = new LinkedList<>();

// 在两端添加
list.addFirst(1);      // O(1)
list.addLast(2);       // O(1)

// 从两端移除
Integer first = list.removeFirst(); // O(1)
Integer last = list.removeLast();   // O(1)

// 查看（不移除）
Integer first = list.peekFirst();   // O(1)，空时返回 null
Integer last = list.peekLast();     // O(1)

// 访问（慢！）
int val = list.get(0); // O(n) - 避免使用！

对比表

操作ArrayListLinkedList
按索引访问O(1)O(n) ❌
末尾添加/移除O(1)O(1)
开头添加/移除O(n)O(1) ✅
中间添加/移除O(n)O(n)
内存开销低高（指针）
使用场景随机访问频繁头尾操作

常见 LeetCode 模式

双指针：

int left = 0, right = list.size() - 1;
while (left < right) {
    // 处理...
    left++;
    right--;
}

有序列表二分查找：

Collections.sort(list);
int idx = Collections.binarySearch(list, target); // O(log n)
// 如果找到返回索引，否则返回 (-(插入点) - 1)

3. Set 操作

HashSet（无序）

适用于快速查找，不关心顺序时。

Set<Integer> set = new HashSet<>();

// 添加元素
boolean added = set.add(1);     // O(1)，已存在返回 false

// 移除元素
boolean removed = set.remove(1); // O(1)

// 检查存在性
boolean exists = set.contains(1); // O(1)

// 大小
int size = set.size();      // O(1)
boolean empty = set.isEmpty(); // O(1)

// 迭代
for (int val : set) {
    // 无序！
}

// 集合运算
Set<Integer> set2 = new HashSet<>(Arrays.asList(2, 3, 4));
set.addAll(set2);           // 并集
set.retainAll(set2);        // 交集
set.removeAll(set2);        // 差集

TreeSet（有序）

适用于维护排序顺序和范围查询。

TreeSet<Integer> set = new TreeSet<>();

// 添加/移除（与 HashSet 相同但 O(log n)）
set.add(5);                 // O(log n)
set.remove(5);              // O(log n)
boolean exists = set.contains(5); // O(log n)

// 有序访问
Integer first = set.first();    // O(log n)，最小元素
Integer last = set.last();      // O(log n)，最大元素

// 范围查询
Integer ceil = set.ceiling(4);  // O(log n)，最小的 >= 4，无则 null
Integer floor = set.floor(4);   // O(log n)，最大的 <= 4，无则 null
Integer higher = set.higher(4); // O(log n)，最小的 > 4
Integer lower = set.lower(4);   // O(log n)，最大的 < 4

// 子集视图
SortedSet<Integer> head = set.headSet(5);    // 元素 < 5
SortedSet<Integer> tail = set.tailSet(5);    // 元素 >= 5
SortedSet<Integer> sub = set.subSet(2, 8);   // 元素 [2, 8)

// 移除首尾
Integer first = set.pollFirst();  // O(log n)，移除并返回
Integer last = set.pollLast();    // O(log n)

LinkedHashSet（插入顺序）

保持插入顺序，具有 HashSet 的性能。

Set<Integer> set = new LinkedHashSet<>();
// 与 HashSet 方法相同，但迭代保持插入顺序

对比表

操作HashSetTreeSetLinkedHashSet
Add/RemoveO(1) ✅O(log n)O(1) ✅
ContainsO(1) ✅O(log n)O(1) ✅
顺序无排序 ✅插入 ✅
范围查询❌✅ ceiling/floor❌
使用场景快速查找有序数据保持顺序

常见 LeetCode 模式

查找重复：

Set<Integer> seen = new HashSet<>();
for (int num : nums) {
    if (!seen.add(num)) {
        // 发现重复！
    }
}

Two Sum 使用 Set：

Set<Integer> seen = new HashSet<>();
for (int num : nums) {
    if (seen.contains(target - num)) {
        return true;
    }
    seen.add(num);
}

4. Map 操作

HashMap（无序）

适用于快速键值查找，不关心顺序时。

Map<String, Integer> map = new HashMap<>();

// 放入元素
map.put("key", 1);          // O(1)，返回旧值或 null
map.putIfAbsent("key", 2);  // O(1)，键不存在时才放入

// 获取元素
Integer val = map.get("key");     // O(1)，未找到返回 null
Integer val = map.getOrDefault("key", 0); // O(1)，带默认值

// 检查存在性
boolean hasKey = map.containsKey("key");   // O(1)
boolean hasVal = map.containsValue(1);     // O(n) - 慢！

// 移除
Integer removed = map.remove("key");       // O(1)，返回旧值

// 大小
int size = map.size();      // O(1)
boolean empty = map.isEmpty(); // O(1)

// 迭代（最佳实践）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

// 仅迭代键
for (String key : map.keySet()) {
    // O(n)
}

// 仅迭代值
for (Integer value : map.values()) {
    // O(n)
}

// 计算方法（Java 8+）
map.merge("key", 1, Integer::sum);  // 增加 1
map.compute("key", (k, v) -> v == null ? 1 : v + 1);
map.computeIfAbsent("key", k -> 0);
map.computeIfPresent("key", (k, v) -> v + 1);

TreeMap（按键排序）

适用于维护键的排序顺序和范围查询。

TreeMap<Integer, String> map = new TreeMap<>();

// 基本操作（与 HashMap 相同但 O(log n)）
map.put(5, "five");         // O(log n)
String val = map.get(5);    // O(log n)
map.remove(5);              // O(log n)

// 有序访问
Integer firstKey = map.firstKey();  // O(log n)，最小键
Integer lastKey = map.lastKey();    // O(log n)，最大键

Map.Entry<Integer, String> firstEntry = map.firstEntry();  // O(log n)
Map.Entry<Integer, String> lastEntry = map.lastEntry();    // O(log n)

// 范围查询
Integer ceilKey = map.ceilingKey(4);  // O(log n)，最小键 >= 4
Integer floorKey = map.floorKey(4);   // O(log n)，最大键 <= 4
Integer higherKey = map.higherKey(4); // O(log n)，最小键 > 4
Integer lowerKey = map.lowerKey(4);   // O(log n)，最大键 < 4

Map.Entry<Integer, String> ceilEntry = map.ceilingEntry(4);
Map.Entry<Integer, String> floorEntry = map.floorEntry(4);

// 子映射视图
SortedMap<Integer, String> head = map.headMap(5);    // 键 < 5
SortedMap<Integer, String> tail = map.tailMap(5);    // 键 >= 5
SortedMap<Integer, String> sub = map.subMap(2, 8);   // 键 [2, 8)

// 移除首尾
Map.Entry<Integer, String> first = map.pollFirstEntry();  // O(log n)
Map.Entry<Integer, String> last = map.pollLastEntry();    // O(log n)

LinkedHashMap（插入/访问顺序）

保持插入顺序或访问顺序（用于 LRU Cache）。

// 插入顺序（默认）
Map<Integer, String> map = new LinkedHashMap<>();

// 访问顺序（用于 LRU Cache）
Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
// 参数：initialCapacity, loadFactor, accessOrder=true

// 重写 removeEldestEntry 实现 LRU 淘汰
Map<Integer, String> lruCache = new LinkedHashMap<Integer, String>(capacity, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > capacity;
    }
};

对比表

操作HashMapTreeMapLinkedHashMap
Put/Get/RemoveO(1) ✅O(log n)O(1) ✅
顺序无排序 ✅插入/访问 ✅
范围查询❌✅ ceiling/floor❌
使用场景快速查找有序键LRU cache

常见 LeetCode 模式

频率映射：

Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.put(c, freq.getOrDefault(c, 0) + 1);
}

滑动窗口与 Map：

Map<Character, Integer> window = new HashMap<>();
int left = 0;
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    window.put(c, window.getOrDefault(c, 0) + 1);
    
    while (/* 条件 */) {
        char d = s.charAt(left);
        window.put(d, window.get(d) - 1);
        if (window.get(d) == 0) window.remove(d);
        left++;
    }
}

5. 堆 / PriorityQueue

PriorityQueue（默认最小堆）

适用于维护 Top K 元素或按优先级处理。

// 最小堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 最大堆（逆序）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// 自定义比较器
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

// 添加元素
pq.offer(5);           // O(log n)，返回 boolean
pq.add(3);             // O(log n)，失败抛出异常

// 移除元素
Integer min = pq.poll();   // O(log n)，空时返回 null
Integer min = pq.remove(); // O(log n)，空时抛出异常

// 查看（不移除）
Integer min = pq.peek();   // O(1)，空时返回 null
Integer min = pq.element(); // O(1)，空时抛出异常

// 大小
int size = pq.size();      // O(1)
boolean empty = pq.isEmpty(); // O(1)

// 移除特定元素（慢！）
pq.remove(5);          // O(n) - 尽量避免！

// 包含（慢！）
boolean exists = pq.contains(5); // O(n) - 避免！

自定义比较器

// 按数组第一个元素比较
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

// 按自定义对象字段比较
class Task {
    int priority;
    String name;
}
PriorityQueue<Task> pq = new PriorityQueue<>((a, b) -> a.priority - b.priority);

// 多个条件
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
    if (a[0] != b[0]) return a[0] - b[0];  // 首先按 a[0]
    return a[1] - b[1];                     // 然后按 a[1]
});

// 使用 Comparator.comparing（Java 8+）
PriorityQueue<Task> pq = new PriorityQueue<>(
    Comparator.comparing(t -> t.priority)
);

对比表

操作PriorityQueue
Add/OfferO(log n)
Poll/RemoveO(log n)
PeekO(1)
Remove specificO(n) ❌
ContainsO(n) ❌
排序最小堆（默认）

常见 LeetCode 模式

Top K 元素：

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) {
        minHeap.poll();  // 移除最小的
    }
}
// minHeap 现在包含最大的 K 个元素
int kthLargest = minHeap.peek();

合并 K 个排序链表：

PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
// 添加每个链表的第一个节点
for (ListNode head : lists) {
    if (head != null) pq.offer(head);
}

while (!pq.isEmpty()) {
    ListNode node = pq.poll();
    // 添加到结果...
    if (node.next != null) pq.offer(node.next);
}

滑动窗口最大值（双端队列的替代方案）：

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
// 存储 [值, 索引] 对

6. String 工具类

String（不可变）

Java 中的字符串是不可变的 - 每次修改都会创建新字符串。

String s = "hello";

// 访问
int len = s.length();           // O(1)
char c = s.charAt(0);           // O(1)

// 子串
String sub = s.substring(1);    // O(n)，"ello"
String sub = s.substring(1, 4); // O(n)，"ell" [包含, 不包含)

// 搜索
int idx = s.indexOf('l');       // O(n)，第一次出现，未找到返回 -1
int idx = s.indexOf("ll");      // O(n)，子串搜索
int lastIdx = s.lastIndexOf('l'); // O(n)，最后一次出现

boolean starts = s.startsWith("he");  // O(k)，k = 前缀长度
boolean ends = s.endsWith("lo");      // O(k)，k = 后缀长度

boolean contains = s.contains("ll");  // O(n)

// 比较
boolean eq = s.equals("hello");       // O(n)，内容比较
boolean eqIgnore = s.equalsIgnoreCase("HELLO"); // O(n)
int cmp = s.compareTo("world");       // O(n)，字典序

// 修改（创建新字符串！）
String upper = s.toUpperCase();       // O(n)
String lower = s.toLowerCase();       // O(n)
String trim = s.trim();               // O(n)，移除首尾空白
String replaced = s.replace('l', 'r'); // O(n)，"herro"
String replaced = s.replaceAll("l+", "L"); // O(n)，正则表达式

// 分割
String[] parts = s.split(",");        // O(n)
String[] parts = s.split(",", 2);     // 限制为 2 部分

// 连接（Java 8+）
String joined = String.join(",", "a", "b", "c"); // "a,b,c"

// 转换
char[] chars = s.toCharArray();       // O(n)
byte[] bytes = s.getBytes();          // O(n)

// 检查空
boolean empty = s.isEmpty();          // O(1)，检查 length == 0
boolean blank = s.isBlank();          // O(n)，检查是否只有空白（Java 11+）

StringBuilder（可变）

用于频繁字符串修改，避免创建大量中间字符串。

StringBuilder sb = new StringBuilder();
StringBuilder sb = new StringBuilder(capacity); // 预分配
StringBuilder sb = new StringBuilder("initial"); // 带初始字符串

// 追加
sb.append("hello");        // O(1) 摊销
sb.append(123);            // O(1)，适用于任何类型
sb.append(true);           // O(1)
sb.append('x');            // O(1)

// 插入
sb.insert(0, "prefix");    // O(n)，在索引处插入

// 删除
sb.deleteCharAt(0);        // O(n)，移除索引处的字符
sb.delete(0, 3);           // O(n)，移除 [start, end)

// 替换
sb.setCharAt(0, 'H');      // O(1)，替换字符
sb.replace(0, 3, "Hi");    // O(n)，替换 [start, end)

// 访问
char c = sb.charAt(0);     // O(1)
int len = sb.length();     // O(1)

// 反转
sb.reverse();              // O(n)

// 转换为字符串
String s = sb.toString();  // O(n)

// 清空
sb.setLength(0);           // O(1)，重置长度

StringBuffer（线程安全）

与 StringBuilder API 相同，但同步（更慢）。仅在需要线程安全时使用。

StringBuffer sbuf = new StringBuffer();
// 与 StringBuilder 方法相同

性能对比

操作StringStringBuilderStringBuffer
拼接/修改O(n) 每次 ❌O(1) 摊销 ✅O(1) 摊销
线程安全✅❌✅
速度多次操作慢⚡ 快较慢（同步）
使用场景少量修改多次修改线程安全

⚠️ 面试提示：如果在循环中构建字符串，总是使用 StringBuilder！

// ❌ 错误 - O(n²)，因为每次拼接都创建新字符串
String result = "";
for (String s : strings) {
    result += s;  // 每次都创建新字符串！
}

// ✅ 正确 - O(n)
StringBuilder sb = new StringBuilder();
for (String s : strings) {
    sb.append(s);
}
String result = sb.toString();

常见 LeetCode 模式

回文检查：

// 方法 1：原字符串双指针
int left = 0, right = s.length() - 1;
while (left < right) {
    if (s.charAt(left) != s.charAt(right)) return false;
    left++;
    right--;
}

// 方法 2：使用 StringBuilder 反转
String reversed = new StringBuilder(s).reverse().toString();
return s.equals(reversed);

字符串构建：

StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
    if (isValid(c)) {
        sb.append(c);
    }
}
return sb.toString();

字符频率：

int[] freq = new int[26];  // 对于小写 a-z
for (char c : s.toCharArray()) {
    freq[c - 'a']++;
}

7. 数组工具类

Arrays 类

数组操作的静态工具方法。

int[] arr = {5, 2, 8, 1, 9};

// 排序
Arrays.sort(arr);              // O(n log n)，原地，升序
Arrays.sort(arr, 0, 3);        // O(k log k)，排序子数组 [0, 3)

// 对象数组使用比较器
Integer[] nums = {5, 2, 8, 1, 9};
Arrays.sort(nums, Collections.reverseOrder());  // 降序
Arrays.sort(nums, (a, b) -> a - b);             // 自定义比较器

// 2D 数组排序
int[][] intervals = {{2, 5}, {1, 3}, {4, 6}};
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // 按第一个元素排序

// 二分查找（必须先排序！）
Arrays.sort(arr);
int idx = Arrays.binarySearch(arr, 8);  // O(log n)
// 如果找到返回索引，否则返回 (-(插入点) - 1)

// 复制
int[] copy = Arrays.copyOf(arr, arr.length);      // O(n)，复制整个数组
int[] copy = Arrays.copyOf(arr, 10);              // O(n)，调整大小（填充 0）
int[] range = Arrays.copyOfRange(arr, 1, 4);     // O(k)，复制 [1, 4)

// 填充
Arrays.fill(arr, 0);           // O(n)，填充整个数组
Arrays.fill(arr, 0, 3, -1);    // O(k)，填充 [0, 3) 为 -1

// 比较
boolean eq = Arrays.equals(arr1, arr2);          // O(n)，浅相等
int cmp = Arrays.compare(arr1, arr2);            // O(n)，字典序

// 多维数组深度相等
boolean eq = Arrays.deepEquals(matrix1, matrix2);

// 转换为字符串
String s = Arrays.toString(arr);                 // "[5, 2, 8, 1, 9]"
String s = Arrays.deepToString(matrix);          // 对于多维数组

// 转换为列表
List<Integer> list = Arrays.asList(1, 2, 3);     // 固定大小列表！
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3)); // 可变

原始数组操作

int[] arr = {1, 2, 3, 4, 5};

// 长度（字段，不是方法！）
int len = arr.length;          // O(1)，没有括号！

// 克隆（浅拷贝）
int[] copy = arr.clone();      // O(n)

// System.arraycopy（最快的复制方式）
int[] dest = new int[5];
System.arraycopy(arr, 0, dest, 0, 5);  // O(n)
// 参数：src, srcPos, dest, destPos, length

Collections 工具类（用于 List）

List<Integer> list = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));

// 排序
Collections.sort(list);                          // O(n log n)，升序
Collections.sort(list, Collections.reverseOrder()); // 降序
Collections.sort(list, (a, b) -> a - b);        // 自定义比较器

// 二分查找（必须先排序！）
Collections.sort(list);
int idx = Collections.binarySearch(list, 8);    // O(log n)

// 最小/最大
int min = Collections.min(list);                // O(n)
int max = Collections.max(list);                // O(n)

// 反转
Collections.reverse(list);                      // O(n)

// 打乱
Collections.shuffle(list);                      // O(n)，随机排列

// 频率
int count = Collections.frequency(list, 5);     // O(n)，计数出现次数

// 填充
Collections.fill(list, 0);                      // O(n)，替换所有元素

// 交换
Collections.swap(list, 0, 4);                   // O(1)，交换两个元素

常见 LeetCode 模式

有序数组双指针：

Arrays.sort(arr);
int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return true;
    else if (sum < target) left++;
    else right--;
}

二分查找模板：

int left = 0, right = arr.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}
return -1;  // 未找到

前缀和：

int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}
// [i, j] 的和 = prefix[j + 1] - prefix[i]

8. 速查表

时间复杂度总结

数据结构添加/插入移除访问/获取搜索备注
ArrayListO(1) 末尾, O(n) 中间O(n)O(1)O(n)适合随机访问
LinkedListO(1) 两端O(1) 两端O(n) ❌O(n)适合头尾操作
HashSetO(1)O(1)-O(1)快速查找，无序
TreeSetO(log n)O(log n)-O(log n)有序，范围查询
HashMapO(1)O(1)O(1)O(1) 键快速键值查找
TreeMapO(log n)O(log n)O(log n)O(log n) 键有序键，范围查询
PriorityQueueO(log n)O(log n)O(1) peekO(n)最小/最大堆
ArrayDequeO(1)O(1)--适合栈/队列

何时使用哪种数据结构

需要通过键快速查找？
├─ 需要顺序？
│  ├─ 是 → TreeMap（排序）或 LinkedHashMap（插入）
│  └─ 否 → HashMap ✅
│
仅需唯一元素？
├─ 需要顺序？
│  ├─ 是 → TreeSet（排序）或 LinkedHashSet（插入）
│  └─ 否 → HashSet ✅
│
需要允许重复的有序序列？
├─ 需要按索引随机访问？
│  ├─ 是 → ArrayList ✅
│  └─ 否 → LinkedList（如果有很多头尾操作）
│
需要 FIFO（队列）或 LIFO（栈）？
└─ ArrayDeque ✅
│
需要总是访问最小/最大值？
└─ PriorityQueue ✅

常见陷阱

陷阱为什么错误解决方案
List<Integer> 上的 list.remove(1)移除索引 1，而不是值 1使用 list.remove(Integer.valueOf(1))
对字符串使用 ==比较引用，而非内容使用 s1.equals(s2)
poll() vs remove()poll() 返回 null，remove() 抛异常了解空值的区别
循环中字符串拼接O(n²) 时间使用 StringBuilder
循环中 LinkedList.get(i)O(n²) 时间使用迭代器或 ArrayList
迭代时修改集合ConcurrentModificationException使用 iterator.remove()
二分查找前忘记排序结果错误总是先排序！
arr.length()编译错误（它是字段）使用 arr.length（无括号）

9. 按数据结构分类的常见面试模式

模式 → 数据结构映射

模式最佳数据结构示例问题
滑动窗口HashMap（频率），Deque无重复字符的最长子串
双指针ArrayList（已排序）Two Sum II，盛最多水的容器
单调栈ArrayDeque（作为栈）下一个更大元素，最大矩形
Top K 元素PriorityQueue第 K 大元素，前 K 个高频元素
频率计数HashMap有效的字母异位词，字母异位词分组
快速查找HashSet包含重复元素，Two Sum
范围查询TreeMap/TreeSet区间和的个数，我的日程安排
LRU CacheLinkedHashMapLRU 缓存（LC 146）
合并 K 个有序PriorityQueue合并 K 个排序链表
图 BFS/DFSArrayDeque（BFS 队列）岛屿数量

10. 结论：你的面试武器库

核心要点

  1. 默认选择：HashMap 用于查找，ArrayList 用于序列，ArrayDeque 用于栈/队列
  2. 需要排序？：使用 TreeMap/TreeSet 自动排序
  3. 构建字符串？：循环中总是使用 StringBuilder
  4. 二分查找？：记得先用 Arrays.sort() 排序
  5. 时间复杂度：了解 O(1) vs O(log n) vs O(n) 操作

练习策略

第 1-2 周：实现每个数据结构的基本操作

  • 创建使用 ArrayList、HashMap、ArrayDeque 的小程序
  • 练习转换（Array ↔ List，String ↔ char[]）

第 3-4 周：解决特定模式的问题

第 5 周+：计时练习并练习解释你的数据结构选择

最后的面试提示

✅ 做：

  • 解释为什么选择特定的数据结构
  • 提及关键操作的时间复杂度
  • 使用现代 API（ArrayDeque 而非 Stack）
  • 考虑边界情况（null、空、重复）

❌ 不要做：

  • 使用遗留类（Vector、Hashtable、Stack）
  • 忘记检查 null/空
  • 混淆方法名（poll vs pop，length vs length()）
  • 不使用 StringBuilder 在循环中修改字符串

准备好掌握 Java 面试了吗？

这份参考指南涵盖了你在 LeetCode 和真实面试中会使用的 90% 的数据结构。收藏本页面，在练习时经常回顾。

想要深入了解特定算法，请查看我的其他文章：二分查找、单调栈和 LRU Cache。

祝你编码愉快！🚀

关于作者：Jackey 在 Microsoft、Booking.com 和 Alibaba 拥有 11+ 年的经验，进行过 500+ 次技术面试。本指南提炼了真实面试场景中的实用知识。

← 返回博客列表