LeetCode Hot 100高频算法题精解：哈希表与双指针实战

1. 算法刷题实战LeetCode Hot 1001-10精解算法刷题是每个程序员进阶的必经之路而LeetCode Hot 100则是其中最经典的题目集合。今天我将分享前10道高频题目的解题思路和Java实现重点解析哈希表、双指针和滑动窗口这三大核心技巧。1.1 两数之和哈希表的经典应用两数之和Two Sum是算法入门的第一道题目但它的解法却体现了哈希表的核心思想。题目要求找出数组中两个数使它们的和等于目标值。class Solution { public int[] twoSum(int[] nums, int target) { MapInteger,Integer mapnew HashMap(); for(int i0;inums.length;i){ if(map.containsKey(target-nums[i])) return new int[]{map.get(target-nums[i]),i}; map.put(nums[i],i); } return new int[]{}; } }关键点解析使用HashMap存储数值, 索引的映射关系遍历时检查target-nums[i]是否存在于map中时间复杂度O(n)空间复杂度O(n)注意不要先填充整个哈希表再遍历这样无法处理重复元素的情况。正确的做法是边遍历边检查。1.2 字母异位词分组哈希表的灵活运用字母异位词Group Anagrams问题需要将字母相同但排列不同的字符串归为一组。class Solution { public ListListString groupAnagrams(String[] strs) { MapString,ListString mapnew HashMap(); for(String str:strs){ char[] cstr.toCharArray(); Arrays.sort(c); String keynew String(c); if(!map.containsKey(key)){ map.put(key,new ArrayList()); } map.get(key).add(str); } return new ArrayList(map.values()); } }优化技巧使用排序后的字符串作为哈希键对于大规模数据可以用字符计数数组作为键效率更高时间复杂度O(nklogk)其中k是最长字符串长度1.3 最长连续序列哈希集合的巧妙使用最长连续序列Longest Consecutive Sequence问题要求在未排序数组中找到最长连续数字序列的长度。class Solution { public int longestConsecutive(int[] nums) { SetInteger setnew HashSet(); for(int num:nums) set.add(num); int max0; for(int num:set){ if(!set.contains(num-1)){ // 确保是序列起点 int currentnum; int count1; while(set.contains(current1)){ current; count; } maxMath.max(max,count); } } return max; } }算法分析使用HashSet去重并实现O(1)查询只从序列起点开始计算避免重复工作时间复杂度O(n)每个元素最多被访问两次2. 双指针技巧的多样应用双指针是解决数组/字符串问题的利器下面几道题展示了它的不同应用场景。2.1 移动零快慢指针的经典案例移动零Move Zeroes要求将所有0移动到数组末尾同时保持非零元素的相对顺序。class Solution { public void moveZeroes(int[] nums) { int slow0; for(int fast0;fastnums.length;fast){ if(nums[fast]!0){ int tempnums[slow]; nums[slow]nums[fast]; nums[fast]temp; slow; } } } }操作要点slow指针指向下一个非零元素应该放置的位置fast指针寻找非零元素交换而非直接赋值可以保持原始数据2.2 盛水最多的容器左右指针的贪心策略盛水最多的容器Container With Most Water需要找到两条线使它们与x轴构成的容器能盛最多水。class Solution { public int maxArea(int[] height) { int left0, rightheight.length-1; int max0; while(leftright){ int area(right-left)*Math.min(height[left],height[right]); maxMath.max(max,area); if(height[left]height[right]){ left; }else{ right--; } } return max; } }为什么移动较矮的一边因为容器的容量由较矮的一边决定移动高的一边不会增加容量而移动矮的一边有可能找到更高的边界。2.3 三数之和排序双指针的完美结合三数之和3Sum要求在数组中找到所有不重复的三元组使其和为0。class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger resnew ArrayList(); Arrays.sort(nums); for(int i0;inums.length-2;i){ if(i0nums[i]nums[i-1]) continue; // 去重 int lefti1, rightnums.length-1; while(leftright){ int sumnums[i]nums[left]nums[right]; if(sum0){ res.add(Arrays.asList(nums[i],nums[left],nums[right])); while(leftrightnums[left]nums[left1]) left; // 去重 while(leftrightnums[right]nums[right-1]) right--; // 去重 left; right--; }else if(sum0){ left; }else{ right--; } } } return res; } }关键细节必须先排序才能使用双指针需要仔细处理重复元素的情况时间复杂度O(n²)空间复杂度O(1)3. 滑动窗口与动态规划3.1 无重复字符的最长子串滑动窗口的典型应用无重复字符的最长子串Longest Substring Without Repeating Characters需要找到不包含重复字符的最长子串。class Solution { public int lengthOfLongestSubstring(String s) { MapCharacter,Integer mapnew HashMap(); int max0, left0; for(int right0;rights.length();right){ char cs.charAt(right); if(map.containsKey(c)){ leftMath.max(left,map.get(c)1); } map.put(c,right); maxMath.max(max,right-left1); } return max; } }窗口维护策略使用HashMap记录字符最后出现的位置当遇到重复字符时调整窗口左边界时间复杂度O(n)空间复杂度O(min(m,n))m是字符集大小3.2 找到字符串中所有字母异位词固定大小的滑动窗口找到字符串中所有字母异位词Find All Anagrams in a String需要在字符串s中找到所有p的字母异位词的起始索引。class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger resnew ArrayList(); if(s.length()p.length()) return res; int[] countnew int[26]; for(char c:p.toCharArray()) count[c-a]; int left0, right0, diffp.length(); for(;rightp.length();right){ char cs.charAt(right); if(count[c-a]0) diff--; count[c-a]--; } if(diff0) res.add(0); for(;rights.length();right,left){ char cs.charAt(left); if(count[c-a]0) diff; count[c-a]; cs.charAt(right); if(count[c-a]0) diff--; count[c-a]--; if(diff0) res.add(left1); } return res; } }优化技巧使用固定大小的滑动窗口长度等于p的长度通过字符计数数组来跟踪匹配情况时间复杂度O(n)空间复杂度O(1)3.3 和为K的子数组前缀和与哈希表和为K的子数组Subarray Sum Equals K需要找到所有连续子数组其和等于k。class Solution { public int subarraySum(int[] nums, int k) { MapInteger,Integer mapnew HashMap(); map.put(0,1); int sum0, count0; for(int num:nums){ sumnum; if(map.containsKey(sum-k)){ countmap.get(sum-k); } map.put(sum,map.getOrDefault(sum,0)1); } return count; } }前缀和原理sum[i,j] sum[0,j] - sum[0,i-1]使用HashMap记录前缀和出现的次数时间复杂度O(n)空间复杂度O(n)4. 高级数据结构应用4.1 滑动窗口最大值双端队列的妙用滑动窗口最大值Sliding Window Maximum需要在每个大小为k的滑动窗口中找到最大值。class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(numsnull||nums.length0) return new int[0]; int[] resnew int[nums.length-k1]; DequeInteger dequenew ArrayDeque(); for(int i0;inums.length;i){ // 移除超出窗口范围的元素 while(!deque.isEmpty()deque.peekFirst()i-k1){ deque.pollFirst(); } // 移除小于当前元素的元素 while(!deque.isEmpty()nums[deque.peekLast()]nums[i]){ deque.pollLast(); } deque.offerLast(i); if(ik-1){ res[i-k1]nums[deque.peekFirst()]; } } return res; } }双端队列策略队列中存储的是索引而非值队列中的元素按从大到小排列时间复杂度O(n)每个元素最多进出队列一次5. 算法刷题经验分享在实际刷题过程中我总结了以下几点经验理解比记忆更重要不要死记硬背解法要理解每个算法背后的思想分类练习按算法类型集中练习比如一周专攻双指针问题反复练习经典题目要多次练习直到能独立写出无bug的代码分析复杂度对每个解法都要能分析时间和空间复杂度边界条件特别注意空输入、极端值等边界情况对于Java开发者还需要注意合理使用集合框架HashMap, HashSet, Deque等注意数组越界和空指针异常字符串操作要小心性能问题如频繁拼接最后提醒算法能力的提升需要时间和耐心建议每天坚持做2-3题长期积累会有显著进步。