Java 数据结构实战LeetCode 20 题高频题解覆盖数组/链表/哈希表 3 大核心在技术面试中数据结构与算法能力往往是区分候选人的关键因素。本文精选 LeetCode 上 20 道高频题目通过 Java 实现深入解析数组、链表和哈希表这三大核心数据结构的应用场景与解题技巧。不同于传统教材的系统性讲解我们采用「以题带练」的方式让学习更贴近实际面试需求。1. 数组篇双指针与滑动窗口的艺术数组是最基础的数据结构但其相关题目却能考察多种解题思路。我们重点分析两类经典问题双指针和滑动窗口。1.1 双指针技巧双指针是处理数组问题的利器尤其适合解决有序数组的相关问题。以下是典型题目及解法题目Two Sum (LeetCode 1)public int[] twoSum(int[] nums, int target) { MapInteger, 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; }滑动窗口模板初始化左右指针右指针扩展窗口满足条件时收缩左指针更新最优解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 MapInteger, 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) { MapCharacter, Character map new HashMap(); map.put(), (); map.put(}, {); map.put(], [); StackCharacter 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(); }解题思路使用哈希表存储括号对应关系利用栈处理括号的嵌套关系最终检查栈是否为空题目Top K Frequent Elements (LeetCode 347)public int[] topKFrequent(int[] nums, int k) { MapInteger, Integer frequencyMap new HashMap(); for (int num : nums) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) 1); } PriorityQueueInteger 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)