我在刷题平台上把这四道高频题放在一起做的时候第一反应是“这不都是基础题吗”真正写完之后才发现问题的关键远不止“会不会写循环”。两数之和、字母异位词分组、最长连续序列、移动零这四道题横跨了面试算法里最经典的两大思维范式用哈希表换时间、用双指针做原地操作。很多候选人单独刷每一道都能AC但进入面试被追问“为什么用这个结构”“为什么不能那样写”时反而答不上来。这篇文章就是想把四道题的完整思考链路拆开讲清楚每道题的暴力解法为什么不行、核心结构为什么选它、代码里的坑在哪里以及它们背后的通用思路如何在其他题目里复用。1. 两数之和HashMap是怎么把暴力解拉进O(n)的1.1 暴力解法的天花板在哪里题目本身不复杂给定一个整数数组和一个目标值找出数组中和为目标值的两个数返回它们的下标。大多数人的第一反应是两层循环外层固定一个数内层往后找另一个数判断两者之和是否等于目标值。public int[] twoSum(int[] nums, int target) { for (int i 0; i nums.length; i) { for (int j i 1; j nums.length; j) { if (nums[i] nums[j] target) { return new int[]{i, j}; } } } return new int[]{-1, -1}; }这段代码逻辑上完全正确时间复杂度却是O(n^2)。面试官看到这个答案下一步一定会问“能不能优化”这就是整道题的核心考点你知不知道哈希表能够在O(1)时间内完成查找。为什么暴力解慢因为对于每个元素你都在重新“扫描”剩下的数组去找它的搭档。数组本身没有索引结构找任何一个值都得线性遍历。如果存在一种结构能让我在O(1)时间内回答“目标值减当前值这个补数是否出现过”那整体就能压到一趟遍历完成。1.2 哈希表的“补数查找”思路哈希表在这里要做的事情非常明确用空间记录前面已经扫描过的元素避免回头线性查找。核心思路是这么转换的我不再固定一个数然后去“找另一个数”而是每走到一个元素nums[i]我关心的是“target - nums[i] 之前有没有出现过”。如果出现过那这一对就是答案如果没出现过就把当前值存进哈希表继续往前走。这里有个很容易被忽略的选型问题为什么用HashMap而不是HashSet因为题目要返回下标HashSet只能告诉你“存不存在这个值”没法告诉你它在数组里的哪个位置。HashMap的value存下标才能在三数之和、四数之和这类变体问题里继续复用。还需要注意一个细节我们存的是“已经扫描过的历史元素”每个元素在存入时它的下标是当时的索引。这样查补数的时候得到的下标一定在当前下标之前天然避免了“同一个元素用两次”的问题。1.3 一遍遍历版本的关键细节经典的一遍遍历写法是这样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); } return new int[]{-1, -1}; }有一个细节值得单独说一下这里必须“先查再存”不能“先存再查”。假设数组是[2, 6, 3, 3]目标值是6如果先把当前元素放进去再检查补数走到第一个3的时候map里已经存了第二个……不对遍历顺序是从左到右。我们考虑[3, 2, 4, 3]目标6。如果先存再查遍历到下标2的元素4时补数2在map里可以查到下标1没问题。真正的坑在于如果先存储当前元素然后检查补数当目标值是当前元素的两倍时就会出问题。比如nums [3, 3]target 6走到下标0先把3存进去然后检查补数3发现map里有3而且就是刚存的那个3于是返回[0, 0]但同一个元素不能用两次。所以“先查再存”不是习惯是一个保证正确性的规则。先查查的是历史数据历史数据里绝对不包含当前下标再存把当前下标纳入历史后续的查找才能覆盖它。这段代码的时间复杂度是O(n)空间复杂度是O(n)。面试中最常见的追问有两个第一如果数组是有序的能不能优化空间可以用双指针从两头往中间逼近空间降到O(1)但前提是题目要求返回下标时得小心排序会打乱原始下标。第二如果要求返回所有不重复的组合而不是一组下标那就得在找到一对后跳过重复值同时继续移动指针这已经是两数之和II、三数之和那边的扩展了。2. 字母异位词分组排序key与计数key的取舍2.1 异位词的本质归并成同一个“特征”题目是指定的场景给你一个字符串数组把字母异位词由相同字母组成的单词分到同一组。例如[eat, tea, tan, ate, nat, bat]结果是[[eat, tea, ate], [tan, nat], [bat]]。这道题真正的第一个思维跳跃是什么叫“字母异位词”从组成上看它们只是同一个字母集合的不同排列。也就是说无论字母怎么打乱顺序每个字母出现的次数完全一致。这是它们的“本质特征”。所以问题变成了怎么把一个字符串映射到一个“与字母顺序无关”的特征值上有了这个特征值就能用HashMap来分组key是特征值value是同组字符串的列表。2.2 排序法最简单但存在常数开销最直觉的特征提取方式是排序把每个字符串的字符排序异位词排序后一定会变成完全相同的字符串。public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { char[] arr s.toCharArray(); Arrays.sort(arr); String key new String(arr); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }这段代码可以AC思路也足够清晰但有一个隐蔽的性能问题对每个字符串都要做一次排序。假设有n个字符串平均每个字符串长度是k时间复杂度就是O(n * k log k)。如果字符串数量很大或者单个字符串很长排序的常数开销会非常明显。面试官如果追问“能不能不做排序”就是在引导你走向计数法。2.3 计数法26位数组编码的核心设计与坑既然异位词的特征是由字母出现次数决定的那我可以统计每个字符的出现次数用这个“频次向量”作为key。因为输入都是小写字母频次向量的长度固定为26。但在具体实现上有一个大坑Java里不能直接把int[]当作HashMap的key。数组的equals方法比较的是引用不是内容。你new两个内容完全一样的int[]在HashMap看来它们是两个不同的key。所以必须把这个频次向量“序列化”成字符串。常见的序列化方案有两种。第一种是全量编码把26个计数用分隔符拼起来StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { sb.append(#).append(count[i]); }例如“eat”编码出来像是“#1#0#0#...#1#...#1...”这个字符串本身很长但长度为固定值乘上一个常数总长度可控。好处是直接、无歧义排序也不用做。坏处是字符串较长在HashMap里做哈希计算时开销偏大。第二种是压缩编码只拼接出现次数大于0的字母和次数比如“a2b1c3”表示两个a、一个b、三个cStringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { if (count[i] 0) { sb.append((char) (a i)).append(count[i]); } }这种编码短一些但也有一个细节要想清楚字母和次数直接拼接会不会产生歧义比如“a12b0c0”和“a1b2c0”会不会撞车不会。因为整个键里字母出现的顺序是固定的a到z每个字母的位置天然作为一个分隔符。字母“a2b1c3”里a、b、c各自带自己的计数解析时看到字母就开始读后面的数字下一个字母出现就是上一位的结束。所以压缩编码是安全的。两种编码方案在LeetCode上都能跑通实际应用中我倾向于压缩编码因为字符串更短HashMap的哈希运算时间更少。完整的计数法实现public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { int[] count new int[26]; for (char c : s.toCharArray()) { count[c - a]; } StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { if (count[i] 0) { sb.append((char) (a i)).append(count[i]); } } String key sb.toString(); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }这里用StringBuilder而非字符串拼接也是性能意识。虽然key看起来不长但在大批量数据下字符串常量池和StringBuilder的差距会被放大。凡是循环内需要动态拼接的都优先用StringBuilder这是写算法题时容易被忽略的基础素养。2.4 两种方案怎么选面试中这道题基本都是让两种方案都聊一遍我先讲排序法因为它最容易理解再抛计数法展示我对复杂度的敏感度。从纯复杂度看方案时间复杂度空间复杂度理解难度排序法O(n * k log k)O(nk)低计数法O(n * k)O(nk)中计数法把排序的log k因子去掉了代价是代码更长还要处理数组编码问题。实际刷题时如果字符串长度很小比如小于100个字符排序法的实际运行时间和计数法差别并不大因为排序基于小数组的常数开销很低。但面试时我更推荐把两种方案都铺垫一下然后根据面试官的方向决定最终写哪种。还有一个变体问题值得提前准备如果输入字符串可能包含大写字母、数字或Unicode字符怎么办小写字母的26位数组就不够用了。这时候要么扩大频次数组范围要么直接退回排序法。能考虑到这一步说明你理解的是“字母异位词”的本质而非答案本身。3. 最长连续序列哈希集合如何甩开排序依赖3.1 为什么排序做法不是最优解题目是给定一个未排序的整数数组找出最长连续序列的长度。比如[100, 4, 200, 1, 3, 2]最长连续序列是1, 2, 3, 4答案是4。很多人一看连续序列立刻想到排序排完序后线性扫描一遍数连续递增的长度。排序的时间复杂度是O(n log n)对于n为10^5甚至10^6的数据这已经是一个相对沉重的成本。题目真正期待的做法是O(n)。为什么能做O(n)因为“连续”这个性质有一个特点它只关心值本身不关心值在数组里的位置。这正好和哈希集合的特性吻合——判断一个值是否存在只需要O(1)。3.2 集合去重与“只从段起点扩展”的巧妙设计先把所有数字放入HashSet去重。接下来遍历集合中的每个数字判断它是不是某个连续段的起点如果num - 1也在集合中说明num不是起点跳过。只有当num - 1不在集合中才从num开始向后逐一查找num 1、num 2……直到断掉记录这个连续段的长度。public int longestConsecutive(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { set.add(num); } int best 0; for (int num : set) { if (!set.contains(num - 1)) { int current num; int length 1; while (set.contains(current 1)) { current; length; } best Math.max(best, length); } } return best; }关键就是这个if (!set.contains(num - 1))。它的作用是确保每个连续段只被扫描一次。假设数组包含1,2,3,4这个连续段那么只有从1进入内层循环时才会把4个数字扫完2、3、4因为前面有数字会直接跳过。这样一来每个数字最多被访问两次一次在集合遍历时判断一次在内层扩展时路过整体时间复杂度保持在O(n)。如果不加这个判断每个头部数字都会向后扩展比如遍历到2时会往外扫3、4遍历到3时又扫4一个连续段被重复扫描多次。最坏情况是数组全连续复杂度会退化到O(n^2)。3.3 边界条件与面试追问这道题的边界和细节相当多面试官很喜欢在这里深挖。第一重复元素问题。如果数组是[1, 2, 2, 3, 4]排序法需要在扫描时跳过重复值而集合版天然去重不会有问题。但如果你用了另一种思路对原始数组排序后扫描重复值会导致长度计算错误这是经典扣分点。第二遍历对象的选择。我写的是for (int num : set)而不是for (int num : nums)。用原始数组遍历在数组存在大量重复元素时会做很多无用的起点判断。用集合遍历天然去掉重复数字省下这部分时间。这个细节虽然不影响复杂度量级但体现出你有没有真正理解集合的语义。第三负数和大整数。哈希集合对负数没有特殊限制contains(num - 1)一样能处理。极端情况如Integer.MIN_VALUE减1会溢出变成Integer.MAX_VALUE理论上会出现误判实际测试数据几乎不可能覆盖这种边界但如果你能在面试中主动提一句“这里没有溢出风险”会显得很严谨。第四空数组。直接返回best的初始值0这个比较容易忽略但必须保证初始值设置正确。还有一种常见追问如果数组非常大内存不够用怎么办这已经超出题目本身范围了可以回答用外部排序或分布式分桶的思路但面试的重点还是考察HashSet的应用。4. 移动零双指针的原地覆盖思想4.1 题目条件和“相对顺序”是切入点题目要求把数组中的所有0移动到末尾同时保持非零元素的相对顺序。比如[0, 1, 0, 3, 12]变成[1, 3, 12, 0, 0]要求在原数组上操作不能复制数组。很多人的第一反应是新建一个数组复制非零元素再补零。在原数组上操作这个限制直接堵死了这条路。这道题考点非常纯粹你会不会用双指针做原地覆盖。这里的关键约束是“保持相对顺序”。如果题目说“可以不保持顺序”那你就可以用一头一尾双指针交换复杂度一样但写法更简单。既然要保持顺序就只能用快慢指针慢指针指向下一个非零元素应该放的位置快指针负责扫描整个数组。4.2 快慢指针两种写法的对比最直观的写法是“覆盖再补零”public void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { nums[slow] nums[fast]; slow; } } while (slow nums.length) { nums[slow] 0; } }思路很清晰第一趟把非零元素按顺序往前挪第二趟把剩余位置全部填成0。这个写法代码少逻辑容易理解面试时可以作为第一版方案讲。另一种写法是“直接交换”利用快指针发现非零元素时与慢指针位置交换public void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { int temp nums[slow]; nums[slow] nums[fast]; nums[fast] temp; slow; } } }两个写法的时间复杂度都是O(n)空间复杂度都是O(1)但我更推荐面试时写交换版。原因有两个第一它全程只用一趟扫描不需要第二趟补零边界条件更少第二交换操作保留了数组的“总元素不变”这一性质以后遇到“移动特定值”类问题可以直接迁移。交换版有一个小细节慢指针和快指针重合时交换就是自我交换不需要处理快指针比慢指针快时慢指针位置一定是0因为之前已经把所有非零值往前移了交换才有实际意义把0交换到后面去。4.3 变体问题删除指定元素、移动其他值移动零本质上是一个“原地删除填充”的模板。把代码里的“nums[fast] ! 0”条件改成“nums[fast] ! val”再做类似处理就变成了“移除指定元素”类问题。如果再加入一个“只保留出现一次的元素”的逻辑就接近“删除排序数组中的重复项”那类题目。其实移动零的思想再往深走一步就是快速排序partition的核心把满足条件的元素集中到区间一端。快速排序的partition在选取基准后要做的事情本质上也是“把小于基准的放左边大于基准的放右边”借助的同样是双指针往中间逼近或快慢指针单向扫描。所以这道题看起来简单却是后面理解快排、荷兰国旗问题的重要基础。面试里我还会主动问清楚一个问题数组里全是0时代码能不能正常运行交换版中slow和fast从头开始连续交换的都是0本身等同于没动能正常结束。覆盖版中第一趟扫描时slow不前进第二趟把所有位置都填成0结果也正确。边界情况想清楚之后代码就不用担心特判缺失。5. 面试实战四道题背后的模式识别5.1 三种题型的快速识别方法四道题全部做完之后我最大的体会是刷题刷到一定量真正重要的不是每道题的代码而是看到题面之后能在几秒内锁定“这题考什么结构”。我给自己总结了一张简单的对照表题目特征首选结构涉及题目无序数组中找配对、找补数HashMap两数之和及其变形同特征物分组、计数HashMap 序列化key字母异位词分组值之间的连续性、存在性判断HashSet最长连续序列原地修改、保持顺序双指针移动零这套识别逻辑是可以迁移的。两数之和的变体是三数之和三数之和往往要排序加双指针因为无序配对问题一旦允许多个结果排序能方便去重字母异位词分组的key设计思路可以迁移到“字符出现次数相同的字符串统计”最长连续序列的集合跳跃法可以迁移到“最长的连续区间覆盖”类问题移动零的双指针可以迁移到“原地移除元素”。5.2 面试时的自检清单我面试别人的时候最怕候选人在白板上写完代码就停一副“肯定AC”的样子。写完代码后必须自己过一遍边界这个习惯比多解十道题都值钱。针对这四道题我会按这样一个清单自查空输入nums为null或长度为0代码会不会报错两数之和里map为空循环不执行返回-1数组可以最长连续序列返回0可以移动零什么都不做可以。单元素数组两数之和不可能有答案移动零元素本身可能是0也可能不是代码都要保证不越界。全部元素相同比如两数之和的目标值是2倍的当前值先查再存防止返回同一个下标移动零的数组全为0交换或覆盖都要正常结束。极端大值求和会不会溢出两数之和里如果不用target - nums[i]而用nums[i] nums[j] target整型溢出时结果会出错每次都用减法差来避开。重复元素字母异位词分组中重复字符串应该放在同一组最长连续序列的去重逻辑是否生效。5.3 跟面试官讲题的三个技巧讲题的顺序也很重要。我的习惯是先讲暴力解一句话带过时间复杂度再讲优化解重点说清楚“为什么选这个数据结构”最后写代码写完立刻讲复杂度。很多人跳过暴力解直接讲最优解看上去聪明但面试官其实无从判断你是怎么想到这个方案的。先说暴力解是展示你分析问题有过程再从暴力解的瓶颈切入讲“瓶颈在查找所以用哈希”“瓶颈在空间所以用原地双指针”逻辑链条就完整了。还有一个容易被忽略的点动手写码之前确认题目限制。两数之和里面试官说的是数组有序还是无序对解法影响非常大移动零里能不能用额外空间直接决定你要不要写就地覆盖。这些前置信息没确认就写常常白写一整块代码。最后是代码风格。算法面试不只是看答案对不对还看你写代码的姿势。HashMap的初始容量可以根据数组大小设置比如new HashMap(nums.length)这是有经验的表现循环里避免无意义的重复计算变量命名用slow、fast、count这些一眼能看懂意思的词不要写a、b、c。我自己把四道题反复刷过几轮之后一个特别明显的感受是它们都不是教你“背一个答案”而是逼你想清楚“为什么这个结构合适”。两数之和逼你理解哈希查找的威力字母异位词分组逼你把复杂对象归约成可比较的key最长连续序列逼你跳出排序惯性移动零逼你在原地操作的限制下寻找最精简的路径。把这四个思维模型吃透再遇到同类型的题你根本不用回忆代码光看题面就能知道方向在哪里。
我在刷题平台上把这四道高频题放在一起做的时候第一反应是“这不都是基础题吗”真正写完之后才发现问题的关键远不止“会不会写循环”。两数之和、字母异位词分组、最长连续序列、移动零这四道题横跨了面试算法里最经典的两大思维范式用哈希表换时间、用双指针做原地操作。很多候选人单独刷每一道都能AC但进入面试被追问“为什么用这个结构”“为什么不能那样写”时反而答不上来。这篇文章就是想把四道题的完整思考链路拆开讲清楚每道题的暴力解法为什么不行、核心结构为什么选它、代码里的坑在哪里以及它们背后的通用思路如何在其他题目里复用。1. 两数之和HashMap是怎么把暴力解拉进O(n)的1.1 暴力解法的天花板在哪里题目本身不复杂给定一个整数数组和一个目标值找出数组中和为目标值的两个数返回它们的下标。大多数人的第一反应是两层循环外层固定一个数内层往后找另一个数判断两者之和是否等于目标值。public int[] twoSum(int[] nums, int target) { for (int i 0; i nums.length; i) { for (int j i 1; j nums.length; j) { if (nums[i] nums[j] target) { return new int[]{i, j}; } } } return new int[]{-1, -1}; }这段代码逻辑上完全正确时间复杂度却是O(n^2)。面试官看到这个答案下一步一定会问“能不能优化”这就是整道题的核心考点你知不知道哈希表能够在O(1)时间内完成查找。为什么暴力解慢因为对于每个元素你都在重新“扫描”剩下的数组去找它的搭档。数组本身没有索引结构找任何一个值都得线性遍历。如果存在一种结构能让我在O(1)时间内回答“目标值减当前值这个补数是否出现过”那整体就能压到一趟遍历完成。1.2 哈希表的“补数查找”思路哈希表在这里要做的事情非常明确用空间记录前面已经扫描过的元素避免回头线性查找。核心思路是这么转换的我不再固定一个数然后去“找另一个数”而是每走到一个元素nums[i]我关心的是“target - nums[i] 之前有没有出现过”。如果出现过那这一对就是答案如果没出现过就把当前值存进哈希表继续往前走。这里有个很容易被忽略的选型问题为什么用HashMap而不是HashSet因为题目要返回下标HashSet只能告诉你“存不存在这个值”没法告诉你它在数组里的哪个位置。HashMap的value存下标才能在三数之和、四数之和这类变体问题里继续复用。还需要注意一个细节我们存的是“已经扫描过的历史元素”每个元素在存入时它的下标是当时的索引。这样查补数的时候得到的下标一定在当前下标之前天然避免了“同一个元素用两次”的问题。1.3 一遍遍历版本的关键细节经典的一遍遍历写法是这样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); } return new int[]{-1, -1}; }有一个细节值得单独说一下这里必须“先查再存”不能“先存再查”。假设数组是[2, 6, 3, 3]目标值是6如果先把当前元素放进去再检查补数走到第一个3的时候map里已经存了第二个……不对遍历顺序是从左到右。我们考虑[3, 2, 4, 3]目标6。如果先存再查遍历到下标2的元素4时补数2在map里可以查到下标1没问题。真正的坑在于如果先存储当前元素然后检查补数当目标值是当前元素的两倍时就会出问题。比如nums [3, 3]target 6走到下标0先把3存进去然后检查补数3发现map里有3而且就是刚存的那个3于是返回[0, 0]但同一个元素不能用两次。所以“先查再存”不是习惯是一个保证正确性的规则。先查查的是历史数据历史数据里绝对不包含当前下标再存把当前下标纳入历史后续的查找才能覆盖它。这段代码的时间复杂度是O(n)空间复杂度是O(n)。面试中最常见的追问有两个第一如果数组是有序的能不能优化空间可以用双指针从两头往中间逼近空间降到O(1)但前提是题目要求返回下标时得小心排序会打乱原始下标。第二如果要求返回所有不重复的组合而不是一组下标那就得在找到一对后跳过重复值同时继续移动指针这已经是两数之和II、三数之和那边的扩展了。2. 字母异位词分组排序key与计数key的取舍2.1 异位词的本质归并成同一个“特征”题目是指定的场景给你一个字符串数组把字母异位词由相同字母组成的单词分到同一组。例如[eat, tea, tan, ate, nat, bat]结果是[[eat, tea, ate], [tan, nat], [bat]]。这道题真正的第一个思维跳跃是什么叫“字母异位词”从组成上看它们只是同一个字母集合的不同排列。也就是说无论字母怎么打乱顺序每个字母出现的次数完全一致。这是它们的“本质特征”。所以问题变成了怎么把一个字符串映射到一个“与字母顺序无关”的特征值上有了这个特征值就能用HashMap来分组key是特征值value是同组字符串的列表。2.2 排序法最简单但存在常数开销最直觉的特征提取方式是排序把每个字符串的字符排序异位词排序后一定会变成完全相同的字符串。public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { char[] arr s.toCharArray(); Arrays.sort(arr); String key new String(arr); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }这段代码可以AC思路也足够清晰但有一个隐蔽的性能问题对每个字符串都要做一次排序。假设有n个字符串平均每个字符串长度是k时间复杂度就是O(n * k log k)。如果字符串数量很大或者单个字符串很长排序的常数开销会非常明显。面试官如果追问“能不能不做排序”就是在引导你走向计数法。2.3 计数法26位数组编码的核心设计与坑既然异位词的特征是由字母出现次数决定的那我可以统计每个字符的出现次数用这个“频次向量”作为key。因为输入都是小写字母频次向量的长度固定为26。但在具体实现上有一个大坑Java里不能直接把int[]当作HashMap的key。数组的equals方法比较的是引用不是内容。你new两个内容完全一样的int[]在HashMap看来它们是两个不同的key。所以必须把这个频次向量“序列化”成字符串。常见的序列化方案有两种。第一种是全量编码把26个计数用分隔符拼起来StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { sb.append(#).append(count[i]); }例如“eat”编码出来像是“#1#0#0#...#1#...#1...”这个字符串本身很长但长度为固定值乘上一个常数总长度可控。好处是直接、无歧义排序也不用做。坏处是字符串较长在HashMap里做哈希计算时开销偏大。第二种是压缩编码只拼接出现次数大于0的字母和次数比如“a2b1c3”表示两个a、一个b、三个cStringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { if (count[i] 0) { sb.append((char) (a i)).append(count[i]); } }这种编码短一些但也有一个细节要想清楚字母和次数直接拼接会不会产生歧义比如“a12b0c0”和“a1b2c0”会不会撞车不会。因为整个键里字母出现的顺序是固定的a到z每个字母的位置天然作为一个分隔符。字母“a2b1c3”里a、b、c各自带自己的计数解析时看到字母就开始读后面的数字下一个字母出现就是上一位的结束。所以压缩编码是安全的。两种编码方案在LeetCode上都能跑通实际应用中我倾向于压缩编码因为字符串更短HashMap的哈希运算时间更少。完整的计数法实现public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { int[] count new int[26]; for (char c : s.toCharArray()) { count[c - a]; } StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { if (count[i] 0) { sb.append((char) (a i)).append(count[i]); } } String key sb.toString(); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }这里用StringBuilder而非字符串拼接也是性能意识。虽然key看起来不长但在大批量数据下字符串常量池和StringBuilder的差距会被放大。凡是循环内需要动态拼接的都优先用StringBuilder这是写算法题时容易被忽略的基础素养。2.4 两种方案怎么选面试中这道题基本都是让两种方案都聊一遍我先讲排序法因为它最容易理解再抛计数法展示我对复杂度的敏感度。从纯复杂度看方案时间复杂度空间复杂度理解难度排序法O(n * k log k)O(nk)低计数法O(n * k)O(nk)中计数法把排序的log k因子去掉了代价是代码更长还要处理数组编码问题。实际刷题时如果字符串长度很小比如小于100个字符排序法的实际运行时间和计数法差别并不大因为排序基于小数组的常数开销很低。但面试时我更推荐把两种方案都铺垫一下然后根据面试官的方向决定最终写哪种。还有一个变体问题值得提前准备如果输入字符串可能包含大写字母、数字或Unicode字符怎么办小写字母的26位数组就不够用了。这时候要么扩大频次数组范围要么直接退回排序法。能考虑到这一步说明你理解的是“字母异位词”的本质而非答案本身。3. 最长连续序列哈希集合如何甩开排序依赖3.1 为什么排序做法不是最优解题目是给定一个未排序的整数数组找出最长连续序列的长度。比如[100, 4, 200, 1, 3, 2]最长连续序列是1, 2, 3, 4答案是4。很多人一看连续序列立刻想到排序排完序后线性扫描一遍数连续递增的长度。排序的时间复杂度是O(n log n)对于n为10^5甚至10^6的数据这已经是一个相对沉重的成本。题目真正期待的做法是O(n)。为什么能做O(n)因为“连续”这个性质有一个特点它只关心值本身不关心值在数组里的位置。这正好和哈希集合的特性吻合——判断一个值是否存在只需要O(1)。3.2 集合去重与“只从段起点扩展”的巧妙设计先把所有数字放入HashSet去重。接下来遍历集合中的每个数字判断它是不是某个连续段的起点如果num - 1也在集合中说明num不是起点跳过。只有当num - 1不在集合中才从num开始向后逐一查找num 1、num 2……直到断掉记录这个连续段的长度。public int longestConsecutive(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { set.add(num); } int best 0; for (int num : set) { if (!set.contains(num - 1)) { int current num; int length 1; while (set.contains(current 1)) { current; length; } best Math.max(best, length); } } return best; }关键就是这个if (!set.contains(num - 1))。它的作用是确保每个连续段只被扫描一次。假设数组包含1,2,3,4这个连续段那么只有从1进入内层循环时才会把4个数字扫完2、3、4因为前面有数字会直接跳过。这样一来每个数字最多被访问两次一次在集合遍历时判断一次在内层扩展时路过整体时间复杂度保持在O(n)。如果不加这个判断每个头部数字都会向后扩展比如遍历到2时会往外扫3、4遍历到3时又扫4一个连续段被重复扫描多次。最坏情况是数组全连续复杂度会退化到O(n^2)。3.3 边界条件与面试追问这道题的边界和细节相当多面试官很喜欢在这里深挖。第一重复元素问题。如果数组是[1, 2, 2, 3, 4]排序法需要在扫描时跳过重复值而集合版天然去重不会有问题。但如果你用了另一种思路对原始数组排序后扫描重复值会导致长度计算错误这是经典扣分点。第二遍历对象的选择。我写的是for (int num : set)而不是for (int num : nums)。用原始数组遍历在数组存在大量重复元素时会做很多无用的起点判断。用集合遍历天然去掉重复数字省下这部分时间。这个细节虽然不影响复杂度量级但体现出你有没有真正理解集合的语义。第三负数和大整数。哈希集合对负数没有特殊限制contains(num - 1)一样能处理。极端情况如Integer.MIN_VALUE减1会溢出变成Integer.MAX_VALUE理论上会出现误判实际测试数据几乎不可能覆盖这种边界但如果你能在面试中主动提一句“这里没有溢出风险”会显得很严谨。第四空数组。直接返回best的初始值0这个比较容易忽略但必须保证初始值设置正确。还有一种常见追问如果数组非常大内存不够用怎么办这已经超出题目本身范围了可以回答用外部排序或分布式分桶的思路但面试的重点还是考察HashSet的应用。4. 移动零双指针的原地覆盖思想4.1 题目条件和“相对顺序”是切入点题目要求把数组中的所有0移动到末尾同时保持非零元素的相对顺序。比如[0, 1, 0, 3, 12]变成[1, 3, 12, 0, 0]要求在原数组上操作不能复制数组。很多人的第一反应是新建一个数组复制非零元素再补零。在原数组上操作这个限制直接堵死了这条路。这道题考点非常纯粹你会不会用双指针做原地覆盖。这里的关键约束是“保持相对顺序”。如果题目说“可以不保持顺序”那你就可以用一头一尾双指针交换复杂度一样但写法更简单。既然要保持顺序就只能用快慢指针慢指针指向下一个非零元素应该放的位置快指针负责扫描整个数组。4.2 快慢指针两种写法的对比最直观的写法是“覆盖再补零”public void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { nums[slow] nums[fast]; slow; } } while (slow nums.length) { nums[slow] 0; } }思路很清晰第一趟把非零元素按顺序往前挪第二趟把剩余位置全部填成0。这个写法代码少逻辑容易理解面试时可以作为第一版方案讲。另一种写法是“直接交换”利用快指针发现非零元素时与慢指针位置交换public void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { int temp nums[slow]; nums[slow] nums[fast]; nums[fast] temp; slow; } } }两个写法的时间复杂度都是O(n)空间复杂度都是O(1)但我更推荐面试时写交换版。原因有两个第一它全程只用一趟扫描不需要第二趟补零边界条件更少第二交换操作保留了数组的“总元素不变”这一性质以后遇到“移动特定值”类问题可以直接迁移。交换版有一个小细节慢指针和快指针重合时交换就是自我交换不需要处理快指针比慢指针快时慢指针位置一定是0因为之前已经把所有非零值往前移了交换才有实际意义把0交换到后面去。4.3 变体问题删除指定元素、移动其他值移动零本质上是一个“原地删除填充”的模板。把代码里的“nums[fast] ! 0”条件改成“nums[fast] ! val”再做类似处理就变成了“移除指定元素”类问题。如果再加入一个“只保留出现一次的元素”的逻辑就接近“删除排序数组中的重复项”那类题目。其实移动零的思想再往深走一步就是快速排序partition的核心把满足条件的元素集中到区间一端。快速排序的partition在选取基准后要做的事情本质上也是“把小于基准的放左边大于基准的放右边”借助的同样是双指针往中间逼近或快慢指针单向扫描。所以这道题看起来简单却是后面理解快排、荷兰国旗问题的重要基础。面试里我还会主动问清楚一个问题数组里全是0时代码能不能正常运行交换版中slow和fast从头开始连续交换的都是0本身等同于没动能正常结束。覆盖版中第一趟扫描时slow不前进第二趟把所有位置都填成0结果也正确。边界情况想清楚之后代码就不用担心特判缺失。5. 面试实战四道题背后的模式识别5.1 三种题型的快速识别方法四道题全部做完之后我最大的体会是刷题刷到一定量真正重要的不是每道题的代码而是看到题面之后能在几秒内锁定“这题考什么结构”。我给自己总结了一张简单的对照表题目特征首选结构涉及题目无序数组中找配对、找补数HashMap两数之和及其变形同特征物分组、计数HashMap 序列化key字母异位词分组值之间的连续性、存在性判断HashSet最长连续序列原地修改、保持顺序双指针移动零这套识别逻辑是可以迁移的。两数之和的变体是三数之和三数之和往往要排序加双指针因为无序配对问题一旦允许多个结果排序能方便去重字母异位词分组的key设计思路可以迁移到“字符出现次数相同的字符串统计”最长连续序列的集合跳跃法可以迁移到“最长的连续区间覆盖”类问题移动零的双指针可以迁移到“原地移除元素”。5.2 面试时的自检清单我面试别人的时候最怕候选人在白板上写完代码就停一副“肯定AC”的样子。写完代码后必须自己过一遍边界这个习惯比多解十道题都值钱。针对这四道题我会按这样一个清单自查空输入nums为null或长度为0代码会不会报错两数之和里map为空循环不执行返回-1数组可以最长连续序列返回0可以移动零什么都不做可以。单元素数组两数之和不可能有答案移动零元素本身可能是0也可能不是代码都要保证不越界。全部元素相同比如两数之和的目标值是2倍的当前值先查再存防止返回同一个下标移动零的数组全为0交换或覆盖都要正常结束。极端大值求和会不会溢出两数之和里如果不用target - nums[i]而用nums[i] nums[j] target整型溢出时结果会出错每次都用减法差来避开。重复元素字母异位词分组中重复字符串应该放在同一组最长连续序列的去重逻辑是否生效。5.3 跟面试官讲题的三个技巧讲题的顺序也很重要。我的习惯是先讲暴力解一句话带过时间复杂度再讲优化解重点说清楚“为什么选这个数据结构”最后写代码写完立刻讲复杂度。很多人跳过暴力解直接讲最优解看上去聪明但面试官其实无从判断你是怎么想到这个方案的。先说暴力解是展示你分析问题有过程再从暴力解的瓶颈切入讲“瓶颈在查找所以用哈希”“瓶颈在空间所以用原地双指针”逻辑链条就完整了。还有一个容易被忽略的点动手写码之前确认题目限制。两数之和里面试官说的是数组有序还是无序对解法影响非常大移动零里能不能用额外空间直接决定你要不要写就地覆盖。这些前置信息没确认就写常常白写一整块代码。最后是代码风格。算法面试不只是看答案对不对还看你写代码的姿势。HashMap的初始容量可以根据数组大小设置比如new HashMap(nums.length)这是有经验的表现循环里避免无意义的重复计算变量命名用slow、fast、count这些一眼能看懂意思的词不要写a、b、c。我自己把四道题反复刷过几轮之后一个特别明显的感受是它们都不是教你“背一个答案”而是逼你想清楚“为什么这个结构合适”。两数之和逼你理解哈希查找的威力字母异位词分组逼你把复杂对象归约成可比较的key最长连续序列逼你跳出排序惯性移动零逼你在原地操作的限制下寻找最精简的路径。把这四个思维模型吃透再遇到同类型的题你根本不用回忆代码光看题面就能知道方向在哪里。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
