我在刷题平台上把这四道高频题放在一起做的时候，第一反应是“这不都是基础题吗”，真正写完之后才发现，问题的关键远不止“会不会写循环”。两数之和、字母异位词分组、最长连续序列、移动零，这四道题横跨了面试算法里最经典的两大思维范式：用哈希表换时间、用双指针做原地操作。很多候选人单独刷每一道都能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) { 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); } 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 List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> 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、三个c：

StringBuilder 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 List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> 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 两种方案怎么选

面试中这道题基本都是让两种方案都聊一遍，我先讲排序法，因为它最容易理解，再抛计数法，展示我对复杂度的敏感度。从纯复杂度看：

计数法把排序的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) { Set<Integer> 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 三种题型的快速识别方法

四道题全部做完之后，我最大的体会是：刷题刷到一定量，真正重要的不是每道题的代码，而是看到题面之后能在几秒内锁定“这题考什么结构”。我给自己总结了一张简单的对照表：

这套识别逻辑是可以迁移的。两数之和的变体是三数之和，三数之和往往要排序加双指针，因为无序配对问题一旦允许多个结果，排序能方便去重；字母异位词分组的key设计思路可以迁移到“字符出现次数相同的字符串统计”；最长连续序列的集合跳跃法可以迁移到“最长的连续区间覆盖”类问题；移动零的双指针可以迁移到“原地移除元素”。

5.2 面试时的自检清单

我面试别人的时候，最怕候选人在白板上写完代码就停，一副“肯定AC”的样子。写完代码后必须自己过一遍边界，这个习惯比多解十道题都值钱。

针对这四道题，我会按这样一个清单自查：

1. 空输入：nums为null或长度为0，代码会不会报错？两数之和里map为空，循环不执行，返回-1数组，可以；最长连续序列返回0，可以；移动零什么都不做，可以。
2. 单元素数组：两数之和不可能有答案；移动零元素本身可能是0，也可能不是，代码都要保证不越界。
3. 全部元素相同：比如两数之和的目标值是2倍的当前值，先查再存防止返回同一个下标；移动零的数组全为0，交换或覆盖都要正常结束。
4. 极端大值：求和会不会溢出？两数之和里如果不用target - nums[i]，而用nums[i] + nums[j] == target，整型溢出时结果会出错，每次都用减法差来避开。
5. 重复元素：字母异位词分组中重复字符串应该放在同一组；最长连续序列的去重逻辑是否生效。

5.3 跟面试官讲题的三个技巧

讲题的顺序也很重要。我的习惯是：先讲暴力解，一句话带过时间复杂度；再讲优化解，重点说清楚“为什么选这个数据结构”；最后写代码，写完立刻讲复杂度。

很多人跳过暴力解直接讲最优解，看上去聪明，但面试官其实无从判断你是怎么想到这个方案的。先说暴力解，是展示你分析问题有过程；再从暴力解的瓶颈切入，讲“瓶颈在查找，所以用哈希”“瓶颈在空间，所以用原地双指针”，逻辑链条就完整了。

还有一个容易被忽略的点：动手写码之前，确认题目限制。两数之和里面试官说的是数组有序还是无序，对解法影响非常大；移动零里能不能用额外空间，直接决定你要不要写就地覆盖。这些前置信息没确认就写，常常白写一整块代码。

最后是代码风格。算法面试不只是看答案对不对，还看你写代码的姿势。HashMap的初始容量可以根据数组大小设置，比如new HashMap<>(nums.length)，这是有经验的表现；循环里避免无意义的重复计算；变量命名用slow、fast、count这些一眼能看懂意思的词，不要写a、b、c。

我自己把四道题反复刷过几轮之后，一个特别明显的感受是：它们都不是教你“背一个答案”，而是逼你想清楚“为什么这个结构合适”。两数之和逼你理解哈希查找的威力，字母异位词分组逼你把复杂对象归约成可比较的key，最长连续序列逼你跳出排序惯性，移动零逼你在原地操作的限制下寻找最精简的路径。把这四个思维模型吃透，再遇到同类型的题，你根本不用回忆代码，光看题面就能知道方向在哪里。