Java 数据结构实战：LeetCode 20 题高频题解，覆盖数组/链表/哈希表 3 大核心

Java 数据结构实战：LeetCode 20 题高频题解，覆盖数组/链表/哈希表 3 大核心

在技术面试中，数据结构与算法能力往往是区分候选人的关键因素。本文精选 LeetCode 上 20 道高频题目，通过 Java 实现，深入解析数组、链表和哈希表这三大核心数据结构的应用场景与解题技巧。不同于传统教材的系统性讲解，我们采用「以题带练」的方式，让学习更贴近实际面试需求。

1. 数组篇：双指针与滑动窗口的艺术

数组是最基础的数据结构，但其相关题目却能考察多种解题思路。我们重点分析两类经典问题：双指针和滑动窗口。

1.1 双指针技巧

双指针是处理数组问题的利器，尤其适合解决有序数组的相关问题。以下是典型题目及解法：

题目：Two Sum (LeetCode 1)

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); } throw new IllegalArgumentException("No solution"); }

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

注意：虽然题目可以用暴力解法（O(n²)），但哈希表能将时间复杂度降至 O(n)

题目：Remove Duplicates from Sorted Array (LeetCode 26)

public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int slow = 0; for (int fast = 1; fast < nums.length; fast++) { if (nums[fast] != nums[slow]) { slow++; nums[slow] = nums[fast]; } } return slow + 1; }

1.2 滑动窗口技术

滑动窗口是解决子数组/子串问题的有效方法，典型题目包括：

题目：Minimum Size Subarray Sum (LeetCode 209)

public int minSubArrayLen(int target, int[] nums) { int left = 0, sum = 0; int minLen = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) { sum += nums[right]; while (sum >= target) { minLen = Math.min(minLen, right - left + 1); sum -= nums[left++]; } } return minLen == Integer.MAX_VALUE ? 0 : minLen; }

滑动窗口模板：

1. 初始化左右指针
2. 右指针扩展窗口
3. 满足条件时收缩左指针
4. 更新最优解

2. 链表篇：指针操作与递归思维

链表问题常考察指针操作和递归思想，以下是两类典型问题：

2.1 基础指针操作

题目：Reverse Linked List (LeetCode 206)

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

题目：Merge Two Sorted Lists (LeetCode 21)

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

2.2 快慢指针应用

快慢指针是解决链表环问题和中间节点问题的标准解法：

题目：Linked List Cycle (LeetCode 141)

public boolean hasCycle(ListNode head) { if (head == null) return false; ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { if (slow == fast) return true; slow = slow.next; fast = fast.next.next; } return false; }

3. 哈希表篇：快速查找与去重

哈希表因其 O(1) 的查找复杂度，成为解决查找类问题的首选数据结构。

3.1 频率统计

题目：Valid Anagram (LeetCode 242)

public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] counter = new int[26]; for (char c : s.toCharArray()) { counter[c - 'a']++; } for (char c : t.toCharArray()) { counter[c - 'a']--; if (counter[c - 'a'] < 0) return false; } return true; }

3.2 缓存设计

题目：LRU Cache (LeetCode 146)

class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; } private void addNode(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(DLinkedNode node) { DLinkedNode prev = node.prev; DLinkedNode next = node.next; prev.next = next; next.prev = prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addNode(node); } private DLinkedNode popTail() { DLinkedNode res = tail.prev; removeNode(res); return res; } private Map<Integer, DLinkedNode> cache = new HashMap<>(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) return -1; moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { DLinkedNode newNode = new DLinkedNode(); newNode.key = key; newNode.value = value; cache.put(key, newNode); addNode(newNode); ++size; if (size > capacity) { DLinkedNode tail = popTail(); cache.remove(tail.key); --size; } } else { node.value = value; moveToHead(node); } } }

4. 综合应用：数据结构组合解题

实际面试中，经常需要组合多种数据结构解决问题：

题目：Valid Parentheses (LeetCode 20)

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

解题思路：

1. 使用哈希表存储括号对应关系
2. 利用栈处理括号的嵌套关系
3. 最终检查栈是否为空

题目：Top K Frequent Elements (LeetCode 347)

public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> frequencyMap = new HashMap<>(); for (int num : nums) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1); } PriorityQueue<Integer> heap = new PriorityQueue<>( (a, b) -> frequencyMap.get(a) - frequencyMap.get(b) ); for (int num : frequencyMap.keySet()) { heap.add(num); if (heap.size() > k) { heap.poll(); } } int[] result = new int[k]; for (int i = k - 1; i >= 0; i--) { result[i] = heap.poll(); } return result; }

关键点：

• 哈希表统计频率
• 最小堆维护 Top K 元素
• 时间复杂度优化至 O(n log k)