企业官网建设流程全解析

1. 训练营第7天的三道题，到底在练什么

训练营进入第7天，今天的三道题——454.四数相加II、383.赎金信、15.三数之和——放在一起刷特别有嚼劲。前两道是哈希表的经典应用，第三道则把双指针和去重玩到了细节深处。如果你最近在准备算法面试，或者刚开始系统刷题，这一天的内容值得停下来认真拆一遍。

很多人刷题只追求把题目跑通，但第7天真正的重点不是AC三道题，而是理解四个关键技术点：为什么四数相加能用分组哈希把O(n^4)降到O(n^2)，为什么赎金信可以用一个长度26的数组搞定，为什么三数之和用哈希法容易翻车而双指针能优雅去重，以及“去重”到底应该发生在哪一层循环里。把这几个点打通，后面遇到四数之和、最接近的三数之和，思路会顺很多。

这三道题适合谁来刷？如果你是刚开始系统刷题的人，454能帮你建立“分组凑对”的直觉，383能让你看到数组比哈希表更轻量的场景，15能逼你把手写去重练熟；如果你已经刷过不少题，今天更多是复盘和对比：同样是“在数组里找组合”，为什么有时候用哈希表，有时候用双指针，判断依据是什么。我自己刷下来的感受是，第7天正好处在“哈希表专题”和“双指针专题”的衔接位置，是特别值得回头再刷一天的题组。

2. 454.四数相加II：四个数组的经典哈希套路

2.1 暴力解法为什么跑不动

题目很直白：给你四个整数数组 A、B、C、D，长度都是 n，从每个数组里各取一个数，问有多少种四元组 (i, j, k, l) 满足 A[i] + B[j] + C[k] + D[l] = 0。

这里先说清楚，为什么题目叫“四数相加II”而不是“四数之和”：因为真正的“四数之和”是在同一个数组里挑四个数，并且结果需要去重；而这道题是四个独立数组，每个数只能从对应数组里取，所以每种下标组合天然不同，不需要去重，只需要计数。换句话说，nums 的数值重复不影响答案，下标不同就算不同元组。

暴力解法是四层循环，O(n^4)。当 n 达到 200 时，200^4 是 16 亿次加法，任何在线判题环境都会超时。有人会先固定前三个数，再用哈希表查第四个数，这样复杂度降到 O(n^3)，看起来可行，但 n=200 时也有 800 万次操作，在 C++ 里勉强能跑，Python 里就很容易卡在超时边缘。所以 O(n^3) 不是理想答案。

真正的突破口是分治。把四个数组分成两组：A+B 一组，C+D 一组。原来的条件：

A[i] + B[j] + C[k] + D[l] = 0

可以改写成：

(A[i] + B[j]) = -(C[k] + D[l])

于是一个“四数相加”问题就被拆成了两个“两数相加”问题。我们只需要把 A+B 的所有组合和出现次数存起来，再遍历 C+D 的所有组合，去哈希表里查对应的相反数。

2.2 分组哈希的具体实现

先做第一步：遍历 A 和 B，用两层循环把所有 A[i]+B[j] 的和存进哈希表，value 是这个和出现的次数。这里必须用“次数”而不是“是否存在”，因为同一个和可能对应多种下标组合。举个例子，如果 A 里有两个不同的 1，B 里有两个不同的 2，那么 A+B 的和为 3 就有 4 种组合。如果哈希表只存布尔值，答案会少算一大截。

第二步：遍历 C 和 D，同样两层循环，计算 sum = C[k]+D[l]，然后去哈希表里查-sum。如果查到了 count 次，说明有 count 个 A+B 组合能和当前的 C+D 配对成 0，答案就累加 count。

这里有一个实现上的习惯问题：为什么只用一组哈希表，而不是把 C+D 也存成哈希表，然后两个表互查？答案是可以，但没必要。只存 A+B，让 C+D 边遍历边查，代码最直观，也不会引入两个表合并的额外麻烦。更关键的是，这样空间上只存了 n^2 个键值对，而不是两倍。

很多人在这一步会忽略一个细节：A+B 的和可能是负数，哈希表的 key 要接受任意整数。这不影响正确性，但写测试用例时会发现，负数 key 的统计和查询完全正常。另一个细节是计数类型，后面单独讲。

2.3 一个具体例子推演

光说思路容易飘，拿一组小数据走一遍就清楚了。假设：

A = [1, 2]
B = [-2, -1]
C = [-1, 2]
D = [0, 2]

先算 A+B 的所有和：

• 1 + (-2) = -1
• 1 + (-1) = 0
• 2 + (-2) = 0
• 2 + (-1) = 1

所以哈希表是：-1 出现 1 次，0 出现 2 次，1 出现 1 次。

再遍历 C+D：

• -1 + 0 = -1，需要查 1，哈希表里有 1 次，答案 +1
• -1 + 2 = 1，需要查 -1，哈希表里有 1 次，答案 +1
• 2 + 0 = 2，需要查 -2，哈希表里没有
• 2 + 2 = 4，需要查 -4，哈希表里没有

最终答案是 2。这两组分别是：A[1]+B[1]+C[0]+D[0] = 2 + (-1) + (-1) + 0 = 0，以及 A[0]+B[0]+C[0]+D[1] = 1 + (-2) + (-1) + 2 = 0。可以看到，计数是关键，因为 0 这个和在 A+B 里出现了 2 次，但恰好 C+D 里没有需要查 0 的情况，所以不影响最终结果；如果 C+D 出现需要查 0 的情况，就会把 2 次一起加进去。

2.4 代码实现与复杂度分析

Python 里最简洁的写法是用 Counter：

from collections import Counter def fourSumCount(A, B, C, D): cnt = Counter() for a in A: for b in B: cnt[a + b] += 1 ans = 0 for c in C: for d in D: ans += cnt.get(-(c + d), 0) return ans

Counter 底层是字典，cnt.get(key, 0)保证了查不到时返回 0，不用额外判断键是否存在。C++ 版本对应的是unordered_map<int, int>，思路一模一样。

复杂度方面，时间上两轮各 O(n^2)，整体 O(n^2)。空间上哈希表最多存 n^2 个不同的和，所以也是 O(n^2)。相比暴力 O(n^4)，这是一个非常经典的“用空间换时间”案例。

还有一个面试加分点：这个解法并不要求 A、B、C、D 长度相等。假设四组长度分别是 a、b、c、d，那么时间复杂度是 a×b + c×d，空间是 a×b。如果面试官问“四个数组长度不一样怎么办”，可以直接答“把较小的两组放前面存表，较大的两组放后面查表，这样空间开销更小”，这种优化会让面试官觉得你真的理解了复杂度，而不只是背题。

3. 383. 赎金信：用数组模拟哈希表

3.1 题目本质是“频次包含”而非“频次相等”

383 的题目场景很有趣：杂志上有一串字符 magazine，你手里有一封勒索信 ransomNote，问能不能用杂志里的字符拼出这封信。

乍一看很多人会误判成“只要 magazine 里出现过所有需要的字符就行”。比如 ransomNote = "aa"，magazine = "aab"，有人觉得两个 a 都出现过，返回 true；这个例子其实也能返回 true，因为 aab 里确实有两个 a。但如果 magazine = "ab"，那就只有一个 a，拼不出两个 a，必须返回 false。核心在于杂志里的每个字符只能用一次，这是一个“频次包含”问题：magazine 中每个字符的出现次数必须大于等于 ransomNote 中对应字符的所需次数。

这个题和 242. 有效的字母异位词很像，但判断逻辑不同。有效字母异位词要求两个字符串的字符频次完全相等，是一种“双向包含”关系；赎金信只要求 magazine 的频次“覆盖”ransomNote，是一种“单向包含”关系。理解这一点，代码逻辑才会有正确的终止条件。

3.2 数组计数实现

题目明确说了字符串只包含小写字母，字符集只有 26 个，所以不需要真正的哈希表，一个长度为 26 的数组就够了。数组下标 0 对应 'a'，1 对应 'b'，以此类推。

标准写法：

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

第一步遍历 magazine，把每个字符出现的次数记录到数组里；第二步遍历 ransomNote，每遇到一个字符就扣掉一次，如果发现扣到 0 以下（也就是当前字符已经不够用），直接返回 False。这个“先统计源，再扣减目标”的套路，和 454 里“先存 AB，再查 CD”本质上是一个思想。

为什么用数组而不是字典？因为字符集固定只有 26 个，数组的下标可以直接算出，不需要计算哈希、不需要处理冲突，随机访问是 O(1)，而且空间复杂度是严格的 O(1)。如果使用HashMap<Character, Integer>，功能是一样的，但常数更大，代码也更重。在面试场景里，主动指出“这里字符集范围很小，所以可以用数组代替哈希表”，是很加分的细节。

3.3 与 242. 有效的字母异位词做对比

如果刷过 242 题，再写 383 会特别快，但要注意两个细节差异。

242 的完整逻辑是：先统计 s 的字符频次，再遍历 t 并扣减，最后还要检查数组里是否还有非零值，只要有任何非零值，就说明频次不相等；而 383 不需要最后全表检查，因为我们在扣减过程中就已经能判断“某个字符不够用”了。换句话说，242 需要在最后做一个“验证相等”，383 只需要在过程中做“验证包含”。

还有一个细节是字符串长度。判断两个字符串是否是异位词，前提是长度必须相等；而赎金信则不一定，ransomNote 的长度可以大于 magazine，但一旦大于，直接返回 false 即可，这个前置判断能省去后面的遍历，也是 383 比 242 多出来的一个剪枝点。

很多初学者会犯的错是把统计方向搞反：先统计 ransomNote，再遍历 magazine 去“凑”。虽然也能实现，但要额外维护“某个字符已经被使用了多少次”的标记，代码会明显变长，而且容易在边界条件下出错。所以这类“从源字符串取字符”的题目，标准姿势永远是先统计源，再检查目标。

3.4 小优化与边界处理

除了长度前置判断，还有几个值得注意的点：

• 如果字符集不只有小写字母，比如包含大写字母和数字，可以把数组扩到 128 或 256，直接用 ASCII 码做下标，连ord(ch) - ord('a')都省了。
• 如果字符集是任意 Unicode，或者题目没限定范围，再退回用HashMap。
• 如果 magazine 或 ransomNote 中有一个为空，逻辑也要成立：空串一定能拼出来，因为不需要任何字符；而 magazine 为空但 ransomNote 非空，一定拼不出来。

这道题很小，但在工程上其实很常见：权限校验里判断“角色拥有的权限集合是否覆盖需要的权限集合”，日志系统里判断“资源配额是否满足请求消耗”，都是同一个频次包含模型。刷题时能想到这一层，说明你不是在背代码，而是在训练建模能力。

4. 15. 三数之和：排序 + 双指针 + 深度去重

4.1 哈希法可行但陷阱多

三数之和是个高频题。题目给一个整数数组 nums，要求找到所有满足 i、j、k 两两不同且 nums[i] + nums[j] + nums[k] = 0 的三元组，并且三元组不能重复。这里的“不能重复”指值不能重复，例如 [-1, 0, 1] 和 [0, 1, -1] 是同一个三元组，只输出一次。

暴力 O(n^3) 肯定不行。常见的错误优化是：固定第一个数，然后用两数之和的哈希法去找后面两个数。这个思路理论上可行，因为三数之和可以拆成“固定一个数 + 两数之和”。但真写起来会遇到两个痛点。

第一个痛点是去重麻烦。如果数组里有重复值，同一个三元组可能被加入多次。常见对策是用Set<List<Integer>>存结果，最后转成列表，这样确实能去重，但哈希集合存储结果对象开销很大，而且代码可读性差。

第二个痛点是哈希表无法自然跳过重复值。找两数之和时，哈希表只能告诉你“有没有”以及“下标是多少”，但无法告诉你“当前这个重复值对应的解是否已经收集过”。于是你会在代码里加各种“跳过重复”的判断，很容易写漏或写错。

所以，虽然哈希法在时间复杂度上也是 O(n^2)，但实际实现和面试讲解都不够优雅。这道题公认的解法是：排序 + 双指针。

4.2 双指针的移动逻辑

双指针的思路分三步：

1. 对原数组排序。
2. 外层循环固定最左边的数 nums[i]。
3. 内层用 left 和 right 两个指针分别指向 i+1 和数组末尾，从两侧向中间移动。

排序是前置条件，只有数组有序，left 和 right 才能根据当前和的大小决定往哪边移动：

• 如果nums[i] + nums[left] + nums[right] > 0，说明整体偏大，需要让 right 往左移动，减小和。
• 如果和小于 0，说明整体偏小，需要让 left 往右移动，增大和。
• 如果和等于 0，记录答案，然后同时移动 left 和 right。

这里有个自动剪枝：因为数组已经排序，如果nums[i] > 0，那么从 i 开始往后的所有数都大于 0，三个正数不可能相加等于 0，直接break整个循环。这个剪枝放在循环开头就能生效，能省掉不少无效遍历。

双指针的复杂度是 O(n^2)，每个 i 对应一次 O(n) 的指针扫描，整体就是 O(n^2)。加上排序 O(n log n)，总时间复杂度还是 O(n^2)，空间上除了排序的栈开销和答案数组，只有常数空间。

4.3 去重到底怎么去

这道题绝大多数人栽在去重上。去重要分两层，缺一不可。

第一层是外层固定元素的去重。当i指向的值和上一个位置i-1的值相等时，说明这个值作为第一个数已经被处理过了，直接continue。

这里有个非常经典的错误：有人会写成nums[i] == nums[i+1]就 continue，看起来也是在跳过重复值，实际上是错的。因为如果数字在i和i+1位置相等，你会在第一次遇到它时就把后面那个相等元素的解一起漏掉。举例，nums = [-1, -1, 2]，i=0 时，nums[0] == nums[1] 如果继续跳过，那么 [-1, -1, 2] 这个合法三元组就永远找不到了。正确写法是比较nums[i] == nums[i-1]，保证“同一个值只会作为第一个数被处理一次”。

第二层是内层指针的去重。当找到一个合法三元组后，left 和 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

注意这里有两个细节。第一，去重的时机是在找到答案之后，不是在寻找过程中。如果在寻找过程中看到重复值就跳过，可能会跳过本应作为组成元素的数，导致漏解。第二，while 循环只会把指针停在最后一个重复值上，所以去重结束后还要再手动执行一次left += 1和right -= 1，否则指针会卡在重复值上，可能又生成重复答案或死循环。

完整代码：

def threeSum(nums): nums.sort() n = len(nums) res = [] for i in range(n): if nums[i] > 0: break if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, n - 1 while left < right: total = nums[i] + nums[left] + nums[right] if total > 0: right -= 1 elif total < 0: left += 1 else: res.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 res

如果 Write C++，步骤完全一样：

vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> result; int n = nums.size(); for (int i = 0; i < n; ++i) { if (nums[i] > 0) break; if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1, right = n - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum > 0) right--; else if (sum < 0) left++; else { result.push_back({nums[i], nums[left], nums[right]}); while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } } } return result; }

4.4 一个样例的完整走查

拿经典样例 nums = [-1, 0, 1, 2, -1, -4] 来手动走一遍。

排序后数组是 [-4, -1, -1, 0, 1, 2]。

i=0，nums[0] = -4，不是重复值，left=1，right=5。此时 nums[0]+nums[left]+nums[right] = -4 + (-1) + 2 = -3，小于 0，left++。left=2，仍然是 -1，和还是 -3，left++。left=3，值是 0，和变成 -4+0+2 = -2，小于 0，left++。left=4，值是 1，和变成 -1，小于 0，left++。left=5，此时 left==right，退出内层循环。这个 i 没有答案。

i=1，nums[1] = -1，和 nums[0] 不同，进入内层。left=2，nums[2] = -1，right=5，nums[5] = 2。和是 -1+(-1)+2 = 0，记录 [-1, -1, 2]。然后内层去重：nums[left]=-1 和 nums[left+1]=0 不相等，不跳；nums[right]=2 和 nums[right-1]=1 不相等，不跳。left++ 到 3，right-- 到 4。此时 nums[1]=-1，left指向 0，right指向 1，和是 -1+0+1=0，记录 [-1, 0, 1]。继续去重：nums[left]=0 和 nums[left+1]=1 不相等；nums[right]=1 和 nums[right-1]=0 不相等；left++ 到 5，right-- 到 3，循环结束。

i=2，nums[2] = -1，因为 nums[2] == nums[1]，外层去重直接 continue。

i=3，nums[3] = 0，left=4，right=5，和是 0+1+2=3，大于 0，right--，right=4，left==right，结束。

最终结果是 [[-1, -1, 2], [-1, 0, 1]]，和预期一致。这个走查过程建议自己手写一遍，尤其注意 i=1 那一步的内层去重，把 left 和 right 的移动路径在纸上画出来，理解会深很多。

5. 三道题放在一起的对比与总结

5.1 复杂度对比表

训练营第7天很适合做横向对比，我用表格把三道题的关键信息列在一起：

从表格能看出，时间上 454 和 15 都是 O(n^2)，但 454 的 O(n^2) 来自两两组合的哈希统计，15 的 O(n^2) 来自外层固定加内层双指针扫描。383 的时间复杂度最低，但没有用到复杂的技巧，纯粹是因为字符集极小，数组可以直接替代哈希。

5.2 什么时候用哈希表，什么时候用双指针

刷完这三道题，我给自己总结了一套判断标准：

第一，如果题目只需要统计数量或判断存在，不需要列出具体组合，优先哈希表。454 就是典型，答案是一个计数，不需要输出每一步的具体下标。

第二，如果需要列出所有具体组合，并且结果要去重，优先排序 + 双指针。15 是典型，哈希表虽然能写，但去重逻辑很容易崩，双指针配合排序可以把重复值连续地跳过去。

第三，如果字符集大小固定且很小，用数组代替哈希表。383 是典型，26 个小写字母，数组比字典快且省内存。

这个判断标准后来帮我解决了不少变体题：四数之和就是把双指针从固定一个元素变成固定两个元素；最接近的三数之和只需要在双指针移动时维护最小绝对差值；“和为 K 的子数组”又回到前缀和加哈希表。你会发现，核心还是那几种套路在组合。

5.3 从这三题抽象出的通用套路

如果要把第7天压缩成一句话，我会说：遇到“多数组凑和”先尝试分组哈希，遇到“单数组找组合”先想想去重难度，遇到“固定字符集统计”直接用数组。

更具体地说，做题时可以按这个顺序思考：

1. 先看数据规模，判断暴力能否通过，不能就考虑降低维度。
2. 再看是否需要去重。需要去重，优先排序 + 双指针；不需要去重，优先哈希表。
3. 最后看字符集或值域是否固定。固定且小，用数组代替哈希表。

这个顺序并不是绝对的，但用在今天这三道题上非常顺。454 不需要去重，所以哈希表是最优选择；15 需要去重，所以双指针胜出；383 字符集固定，所以数组才是最优解。

6. 训练营第7天的实战心得与避坑记录

6.1 三道题的真实踩坑点

第7天刷完，我把自己的错误和我看到别人常犯的错误汇总了一下：

• 454 的答案类型。极端情况下 n=200，如果所有组合都满足条件，答案数量是 200^4 = 1.6e9，刚好还在 32 位 int 的范围内（约 21 亿），但 Python 无所谓，C++/Java 建议直接用 long，避免边界尴尬。
• 454 的计数方向。有人会把 A+B 和 C+D 都存进哈希表，再去找交集。实际没必要，一组存入、一组查询是最简形式，而且空间省一半。
• 383 的索引计算。Python 里必须是ord(ch) - ord('a')，忘记 ord 会报错；C++ 里ch - 'a'可以直接用，因为字符本质是 ASCII 码。
• 15 的外层去重条件。写成nums[i] == nums[i+1]是经典错误，会漏掉 [-1, -1, 2] 这类解。正确写法是nums[i] == nums[i-1]。
• 15 的内层去重之后忘记再走一步。很多人在 while 跳完重复后直接结束本轮，导致 left 或 right 停在重复值上，外层循环可能会重复添加结果。必须手动再left++和right--。

6.2 常见问题速查表

我把这些坑整理成一张速查表，方便之后复习：

6.3 后续还能怎么延伸

如果你能把这三题吃透，接下来的延伸路线会很顺畅。

18.四数之和可以看成 15 的双指针扩展：先排序，外层固定两个数，内层再用左右指针找另外两个数，去重逻辑也嵌套变成两层。最接近的三数之和只需要在双指针移动时维护最小差值，不需要真正的去重，但要记录最接近的结果。还有 454 的变体，比如“四数相加最接近目标值”，也能沿分组哈希的思路做扩展。

我个人建议是，第7天不要急着刷更多新题。把 15 题从零开始，不看任何答案，自己完整写三遍。第一遍允许犯错，第二遍对照代码改错，第三遍关掉编辑器，在白纸上手写完整代码和去重注释。这个“三遍法”我第一次用的时候觉得很枯燥，但效果确实好，尤其是去重这种容易出细节逻辑的题，多写几遍之后肌肉记忆就形成了。

如果你也在训练营里，或者自己按这个节奏刷题，今天不妨多花点时间在“为什么”上：为什么 454 不需要去重，为什么 15 需要去重，为什么 383 的终止条件比 242 简单。把这些为什么都回答了，第7天就算没白过。