企业官网建设流程全解析

哈希表这块，到Part02基本就是硬仗了。Day7的内容放在整个算法训练营的节奏里看，恰好是从“会用哈希表”过渡到“会选哈希表”的分水岭。前面Part01大家已经熟悉了数组、set、map的基本操作，但真正在LeetCode上做题，你会发现哈希表单独出现的概率其实没那么高，更多时候它是和双指针、排序、模拟这些手段混在一起用的。这一天的四道题——四数相加、赎金信、三数之和、四数之和，恰好把“哈希表与其他解法如何取舍”这件事讲透了。

1. 先聊清楚：这一天题目背后的设计逻辑

1.1 为什么Part02选的偏偏是这四道题

很多人刷题有个误区，觉得题目难度越高越值得做。但实际上，训练营安排的题目往往有非常明确的教学意图。Day7的四道题，按顺序是：

• 四数相加II（454题）
• 赎金信（383题）
• 三数之和（15题）
• 四数之和（18题）

这个顺序不是随便排的。四数相加是第一道“哈希表思路能直接秒杀”的题，而且它涉及一个非常重要的思想：分组降维。赎金信看起来简单，但它考察的是“哈希表什么时候优于其他解法”的判断力，属于典型的易错题。三数之和和四数之和则是重头戏，因为你会发现，最优解压根不用哈希表，反而用双指针。把这几道题放在一起，核心目的就是让你建立一种“先分析，再定解法”的习惯，而不是看到“求和”就条件反射地往上套哈希表。

1.2 哈希表和双指针在这个阶段的优先级

我得先把结论放在前面：三数之和、四数之和这两道题，训练营的标准要求是必须掌握双指针解法，哈希表解法可以作为拓展了解。为什么？因为哈希表在“去重”这件事上非常痛苦，你去重需要大量额外的判断逻辑，代码很容易写成一堆if堆叠，面试或笔试时也会显得思路混乱。双指针配合排序，去重逻辑会清爽很多。

但四数相加II这道题不一样，它明确适合用哈希表，因为它的四个数组是独立的，不需要考虑去重问题。哈希表的优势在于“快速定位是否存在以及出现了多少次”，凡是能拆成“两组两两配对”的场景，它都特别合适。所以我一直跟学员说，刷题最重要不是背模板，而是搞清楚每道题最适合的几种解法到底是什么，以及为什么是它们。

2. 四道题的核心思路与实操拆解

2.1 四数相加II：哈希表的教科书式用法

这道题背景很简单：给你四个长度相同的整数数组，从每个数组里各取一个数，有多少种组合能让四个数相加等于0。暴力解法是四层循环，复杂度O(n^4)，遇到几百长度的数组直接算到天荒地老。

核心思路是分组。把四个数组分成两组：A和B一组，C和D一组。先遍历A和B，把所有两数之和放入一个哈希表，key是“和的值”，value是“这个和出现的次数”。再遍历C和D，计算它们的和的相反数，去哈希表里查这个相反数是否存在，如果存在，就把对应的次数累加到结果里。

def fourSumCount(A, B, C, D): count_map = {} for a in A: for b in B: s = a + b count_map[s] = count_map.get(s, 0) + 1 result = 0 for c in C: for d in D: target = -(c + d) if target in count_map: result += count_map[target] return result

这个写法的时间复杂度是O(n^2)，空间复杂度也是O(n^2)。为什么它比直接四层循环快？因为两两分组之后，我们只用遍历两次两两组合，也就是2倍的n^2，而不是n^4。用一个生活化的类比：你要从四副牌里各抽一张凑出某个点数，如果一上来就抽四张，组合数量是天文数字；但如果先把前两副牌的所有组合点数登记在册，再拿后两副牌的组合去对账，瞬间就把问题缩小到了一个可以接受的范围。

实操中有几个细节我必须强调：

• 字典的get方法比if key in dict再取值的写法更简洁，但不代表那个写法就错。建议新手先把逻辑理清，再用get简化。
• 这道题不关心组合的具体元素是什么，只关心组合的数量，所以value存次数就足够了。很多同学一开始会自然想存“组合的下标组合”，但在这里完全不需要。
• 数据范围允许数字和结果为负数，所以哈希表的key可以是负数，不用做偏移处理。

2.2 赎金信：什么时候该用哈希表，什么时候数组更香

赎金信这道题，题意是你有一本杂志字符串和一个赎金信字符串，问赎金信能不能由杂志里的字符拼出来，每个字符只能用一次。刷题经验少的人看到“字符出现次数”，第一反应就是建哈希表。

但仔细想想，这里的字符集范围是什么？题目限定是小写英文字母，也就26个。对于这种“元素范围非常有限且已知固定”的场景，用数组当哈希表才是最优解。数组的下标天然就是字符的映射，只需要把字符的ASCII码减去‘a’的值作为下标，就能实现O(1)的存取，而且完全不需要处理哈希冲突，速度更快，内存消耗也更稳定。

def canConstruct(ransomNote, magazine): record = [0] * 26 for ch in magazine: record[ord(ch) - ord('a')] += 1 for ch in ransomNote: index = ord(ch) - ord('a') if record[index] == 0: return False record[index] -= 1 return True

这道题我觉得真正值得学的不是解法本身，而是**“数据范围决定数据结构”**这个思维。哈希表（字典）是什么时候都用得上的万能工具箱，但万能不代表最优。当你看到“小写字母”“26个字母”“0到100之间的整数”这类限定词，就应该立刻想到数组。反之，如果字符集很大、不确定，或者key的类型是字符串、元组这种复合结构，再用真正的哈希表。

实操中容易踩的坑：

• 忘记先遍历杂志再遍历赎金信，顺序反了会导致误判。
• 只统计了杂志里每个字符是否有，而没统计足够数量。比如杂志有两个‘a’，赎金信要三个‘a’，如果只存布尔值就会出错。
• 直接用Python的Counter后，用减法判断剩余值是否为负数，这种思路也可以，但底层原理仍然是哈希表。我自己更喜欢数组版，因为它连哈希碰撞的担忧都没有。

2.3 三数之和：双指针才是正解，哈希表为何反成累赘

三数之和是这一天的核心难点。题目要求：给你一个整数数组，找出所有不重复的三元组，使得三元组的和为0。注意“不重复”三个字，这是整道题最折磨人的地方。

先看哈希表的思路：固定一个数，然后对剩下的两个数用类似两数之和的方法去哈希表中查找。但问题来了，查到的结果里可能包含同一个元素用了两次的情况，也需要处理重复元素导致的三元组重复问题。最后的去重逻辑非常恶心，可能要同时维护多个set，代码长度暴涨，而且极其容易漏掉边界条件。

双指针解法就清爽得多。第一步先排序，然后固定一个指针i从左往右遍历，作为三元组第一个数。接着在i右侧区间用left和right两个指针相向而行，找两个数与nums[i]的和为0。每找到一个合法三元组，就移动指针，并且跳过所有重复值。

def threeSum(nums): nums.sort() result = [] n = len(nums) for i in range(n): if nums[i] > 0: break if i > 0 and nums[i] == nums[i - 1]: continue left = i + 1 right = n - 1 while left < right: total = nums[i] + nums[left] + nums[right] if total > 0: right -= 1 elif total < 0: left += 1 else: result.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return result

为什么排序以后就简单了？因为有序数组天然具备了“大了往左缩，小了往右扩”的能力。三个数的和如果大于0，说明右边的数太大了，要右指针左移；小于0，说明左边的数太小了，要左指针右移。这个过程本质上是在有序空间里做二分式逼近，逻辑清晰，去重也容易——只要保证同一个数值只被当作同一位置元素用一次就行。

去重的核心有两条：

• 外层循环i去重时，必须用nums[i] == nums[i - 1]判断，而不是nums[i] == nums[i + 1]。因为后者会跳过i本身作为三元组起点的可能性。我见过太多人在这里写反导致结果缺失。
• 找到一组结果后，left和right各自跳过重复值时，跳完还要再各自移动一步，否则会陷入死循环。很多人写完跳过逻辑忘了最后那两行left += 1和right -= 1，然后对着超时报错发懵。

这道题用双指针的复杂度是O(n^2)，排序的O(n log n)可以忽略不计。哈希表做法的复杂度也是O(n^2)，但常数项大得多，而且去重极其费劲。所以训练营里我强烈建议大家至少把双指针版本背下来，面试里能写对，比写得“别出心裁”重要得多。

2.4 四数之和：双指针法的进阶变形与其他关键取舍

四数之和可以看作三数之和的套娃版。核心思路是在三数之和的外面再套一层循环，先固定两个数，剩下的区间仍然用双指针去逼近。

def fourSum(nums, target): nums.sort() result = [] n = len(nums) for i in range(n): if i > 0 and nums[i] == nums[i - 1]: continue for j in range(i + 1, n): if j > i + 1 and nums[j] == nums[j - 1]: continue left = j + 1 right = n - 1 while left < right: total = nums[i] + nums[j] + nums[left] + nums[right] if total > target: right -= 1 elif total < target: left += 1 else: result.append([nums[i], nums[j], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return result

这里有一个非常关键的细节，是很多讲解会一带而过的：这里去重为什么用nums[i] == nums[i - 1]而不是nums[i] == nums[i + 1]，原理和前面三数之和完全一样。你固定的是当前这一层循环的起点，如果和上一个已经处理过的数相同，说明从它开始的所有组合在前一轮已经枚举过了，跳过它才能避免重复。而如果去比较nums[i]和nums[i + 1]，会直接误伤，因为i + 1位置在今后的遍历中还有机会作为“当前层起点”被合法使用。

四数之和还有个额外需要注意的点：target不再是0，可能是任意整数，所以剪枝条件不能写死成nums[i] > target就break。比如全是负数且target是负数的时候，第一个数大于target但仍然可能有解。解决方法是只有在target为正的前提下才做这种提前终止，或者干脆不做剪枝，直接完整遍历。面试时为了减少出错，我个人的习惯是只在确定条件安全时加剪枝，拿不准就先不加。

从复杂度看，四数之和是O(n^3)，这也是双指针法能到达的上限了。如果n是几百还勉强能扛，几千以上就会很吃力，但那种规模通常会有其他专门解法，面试不常考。

2.5 对比总结：三道求和题，三种不同的解法倾向

把这三道题放在一起看会特别有意思。四数相加II用哈希表轻松解决，三数之和用双指针最优，四数之和是三数之和的扩展版。它们看起来都是“几个数相加等于某个值”，但内部逻辑完全不同。

原因是什么？关键在于“多个数组还是单一数组”以及“要不要去重”。

• 多个独立数组，每组内部取一个数：适合分组+哈希表，因为不需要考虑索引互斥问题。
• 单一数组内部选几个数：天然存在“同一元素不能用两次”的限制，还有“三元组/四元组不能重复”的约束，这时哈希表的快速查找优势就被去重成本抵消了。
• 双指针法必须建立在有序数组之上，如果题目不允许排序（比如要求保持原数组顺序），那就得另想办法。但这三道题里不存在这个限制。

建议把这四道题的解法倾向整理成一张表，放在自己的刷题笔记里：

3. 完整实操流程：从读题到AC的关键细节实录

3.1 什么时候该先排序，什么时候绝不能排序

刷完这几道题，一个很自然的疑问是：我拿到一道题，怎么判断能不能排序？我的经验是，只要题目允许改变数组本身顺序，并且不用返回原始下标，那排序通常都是可以接受的。三数之和、四数之和就是这样，你关心的是数值组合，而非位置信息。

但四数相加II不一样，它让你从四个数组里各挑一个数，看起来好像也可以排序？排序数组本身不影响结果正确性，但问题是排序并不能像双指针那样帮你降低复杂度，因为四个数组仍然是独立的，双指针没法跨数组形成单调区间。贸然排序只会增加无谓的O(n log n)开销。所以我的判断流程大概是：

• 先问：题目要返回集合本身还是集合数量？
• 再问：是否涉及“同一数组内多个元素组合”？
• 如果答案是“同一数组内组合”，考虑排序+双指针；如果答案是“多个独立数组”，考虑分组哈希表。

这个流程不能保证100%命中最优解，但能让你在面试的紧张状态下快速找到一个方向，比当场瞎试强得多。

3.2 去重操作的三个常见翻车现场

去重是这几道题真正的分水岭。我总结过学员最容易翻车的三个地方，每次都值得拿出来说：

第一个翻车现场：外层循环用if nums[i] == nums[i + 1]: continue。这会导致你跳过一些原本合法的组合。举个例子，数组是[-1, -1, 2]，target是0，唯一合法三元组就是(-1, -1, 2)。如果i=0时你去比较nums[0]和nums[1]，发现都是-1就跳过了，这个合法结果就永远找不到了。正确的去重是在处理完当前值后，用while nums[i] == nums[i - 1]来跳过后续重复的起点。

第二个翻车现场：内层指针去重时，跳过重复后没有再多走一步。参考前面三数之和的代码，在while跳过重复值后，必须再执行left += 1和right -= 1。如果忘了，left或right仍然指向已经处理过的值，虽然逻辑上不影响正确性，但会导致死循环，或者同一个组合被重复添加。

第三个翻车现场：把去重放在添加到结果之前，而不是之后。去重必须发生在你已经成功找到一组结果之后，因为只有找到结果时，你才知道当前left和right指向的值已经“用过一次”了，后续再遇到相同值必须跳过。如果你一进循环就无脑去重，可能会漏掉合法的组合。

这个坑我当年自己也踩过，后来总结出的规律是：去重的位置永远紧跟在“处理完当前合法状态”之后，而不是之前。这个原则对所有双指针去重都适用。

3.3 花10分钟建立你自己的“哈希表题目识别清单”

经过这一天，我认为每个刷题的人都应该建立一套自己的识别清单。我的清单是这样写的：

• 是否存在多组数据需要配对？如果是，考虑分组哈希表。
• 是否涉及统计元素出现次数，且数据范围已知且固定？如果是，考虑数组代替字典。
• 是否需要在单一数组内找组合且去重？如果是，优先考虑排序+双指针。
• 是否只关心“是否存在”而不关心“有多少”或“具体哪个”？如果是，可以用set。
• 是否有键值对应关系需要快速查找？如果是，用字典，但要注意value存什么（次数、下标、组合）由题目要求决定。

这套清单花不了多少时间，但能把你的思考路径固定下来。我见过太多人刷题靠感觉，看到题就上手写代码，写到一半发现解法不好再推翻重来，非常浪费时间。先花三分钟想清楚方向，再动手写，效率能提升一大截。

4. 一天训练营下来，最常见的疑问与排查经验

4.1 为什么我的四数相加结果总比答案少或者多

这个问题绝大多数情况下出在value的存储语义上。哈希表的value存的到底是“组合出现的次数”还是“有没有出现”，决定了你能不能在第二段循环中直接累加。如果用set存储两数之和，那么当A、B两两组合出现多个相同和的时候，set只保留一个，最终结果就会比答案少。反之，如果你统计次数时，把相同和的不同组合都分别加一，那查询的时候累加次数就是对的。

有一个很容易被忽略的细节：count_map[s] = count_map.get(s, 0) + 1这行代码，看起来简单，但它默认了同一个和会被多次记录。如果写成if s not in count_map: count_map[s] = 1，那么相同的和合并成一次，查询阶段就会少统计。这个问题十个人里有三四个会犯，不是不懂，而是写得太快。

排查方法很简单：打一个日志，输出每个和出现的次数是否与嵌套循环的匹配结果一致。或者直接拿小规模样例手动验证，比如四个数组各两个元素，总共2^4=16种组合，手算也能核对。

4.2 三数之和超时，是不是我的剪枝逻辑写错了

超时的原因通常不是剪枝写错，而是压根没做剪枝，或者去重循环写得有问题导致死循环。先看你的外层循环：当nums[i] > 0的时候，由于数组已经排序，后面的数只会更大，三数之和必然大于0，可以直接break。但如果target不是0，这个条件就不能用。

再看内层双指针：如果当前三数之和大于0，要让right左移；小于0，要让left右移。这个移动逻辑如果写反，left和right就永远不会收敛，循环会无限执行，直到超时。这种情况调试的时候最好在循环里打印left和right当前值，一看就明白。

还有一种隐蔽的导致超时的情况：去重循环里用了while nums[left] == nums[left + 1]但忘记检查left < right的边界，当指针碰撞时还会访问越界元素。Python虽然不会崩溃，但可能读到错误值，导致后续逻辑错乱。所有while去重都必须带上left < right条件，这是铁律。

4.3 赎金信这类题，用字典和用数组到底差多少

说实话，LeetCode的测试数据下，字典和数组的耗时差距并不夸张。但在严格的面试中，面试官想看的是你有没有“数据结构选择意识”。你说“字符集固定且很小，所以我用数组”，这句话比代码本身更能证明你的基本功。反之，如果你每次碰到统计字符都用字典，虽然不算错，但会让人觉得你对底层数据结构理解不够细腻。

我自己的判断标准是：如果key是长度确定的有限枚举类型，就用数组；如果key是任意可哈希对象，才用字典。记住这个标准，你自然知道什么时候该用哪个。

还有一个可以提的小技巧：Python里统计字符频率，如果非要用字典，可以用collections.Counter，它本质上就是字典的封装，但代码更简洁。但训练营阶段我始终建议先用最底层的方式手写一遍，这样你才能理解Counter到底帮你做了什么。

4.4 四数之和里，两层循环的去重分别该注意什么

四数之和比三数之和多了一层循环，去重容易乱。我的记忆方法是：每一层循环的去重，都是和“同一层上一次处理过的值”比较，而不是和“下一层的起始值”比较。

第一层循环i，要和nums[i - 1]比，因为i是第一个数的起点。第二层循环j，要和nums[j - 1]比，但注意这里j的起始值是i + 1，所以判断条件应该是j > i + 1的情况下才去比nums[j] == nums[j - 1]。如果没有j > i + 1这个条件，第一轮循环j等于i+1时，j-1等于i，会和nums[i]本身比较，导致第一个j被误跳过。

我发现很多学员在这个地方错得非常统一，就是少了j > i + 1的判断。只要把这个细节记住，四数之和的去重问题基本解决了一大半。

内层双指针的去重逻辑和三数之和完全一样，不需要额外调整。整体来看，四数之和其实就是三数之和的“一次封装”，把三数之和的核心代码理解透，四数之和是水到渠成的事。

5. 任务驱动复盘：Day7的实际吸收要点与扩展方向

5.1 学完这一天，你真正要带走的三项核心能力

第一项能力是“分组降维”的思维。四数相加II表面上是哈希表题，本质上是把四维问题拆成两个二维问题。这种思想在后面的很多题目里都会反复出现，比如把二维矩阵的某些问题转化为一维问题，把复杂条件拆成两个独立条件分别处理。学完这一天，你应该能熟练地把“多数组配对”问题拆开来看。

第二项能力是“排序后双指针”的操作模式。三数之和、四数之和只是这种模式的两个代表，后面还有更多题目会用排序+双指针去替代哈希表或暴力枚举。掌握了这个模式，你在面对“组合求和”“区间统计”这类问题时就有了一个非常强力的工具箱。

第三项能力是“根据数据范围选择数据结构”的判断力。赎金信告诉我们，不是所有“统计字符”都要用字典。这种判断力需要反复练习才能内化，但每做一道题，它就会更牢固一点。

5.2 后续建议：把这道课的题作为模板题的延展练习

我非常建议你在学完这一天后，回头做几道变体题来检验掌握程度。比如把三数之和改成“最接近的三数之和”，这需要你调整双指针的收敛条件，把“等于target”改成“更新最小差值”。再比如把“三数之和为0”扩展到“三数之和为target”，你只需要调整剪枝逻辑。这种小变化可以对冲“只会背模板”的问题，帮助你真正理解每一行代码的作用。

我自己带过的学员里，凡是能把三数之和的代码逐行讲出为什么的，后面做四数之和基本没什么障碍；凡是背答案的，换一个条件就乱套。刷题最忌“背过了但没理解”，训练营的意义就是帮大家把“我好像会了”变成“我真的会了”。

最后再分享一点个人感受：哈希表Part02这一天，内容确实密集，难度也确实上来了，但它是那种“今天痛苦，明天受益”的知识点。坚持下去，等你把双指针和哈希表的分工想明白了，后面的很多题目会突然变得通透了。