企业官网建设流程全解析

1. 算法训练营第七天：哈希与双指针实战

今天继续代码随想录算法训练营的第七天内容，主要解决四个经典问题：454.四数相加II、383.赎金信、15.三数之和和18.四数之和。这几个问题涵盖了哈希表和双指针两大核心算法技巧，是面试中的高频考点。我会结合自己的刷题经验，详细解析每个问题的解题思路和实现细节。

2. 454.四数相加II：哈希表的巧妙应用

2.1 问题重述与初步分析

给定四个整数数组nums1、nums2、nums3和nums4，数组长度都是n。我们需要计算有多少个元组(i,j,k,l)满足： nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

最直观的暴力解法是四重循环，时间复杂度O(n^4)，这在n=200时显然不可行（200^4=1,600,000,000次运算）。我们需要更高效的解法。

2.2 哈希表优化思路

关键观察：可以将问题拆分为两部分，先计算nums1和nums2的所有可能和，再在nums3和nums4中寻找对应的补数。具体步骤：

1. 遍历nums1和nums2，计算所有a+b的和，并用哈希表记录每个和出现的次数
2. 遍历nums3和nums4，计算所有c+d的和，在哈希表中查找-(c+d)的计数
3. 将所有匹配的计数累加得到最终结果

这种方法将时间复杂度降为O(n^2)，空间复杂度也是O(n^2)。

2.3 代码实现与细节

def fourSumCount(nums1, nums2, nums3, nums4): from collections import defaultdict sum_map = defaultdict(int) count = 0 # 计算nums1和nums2的所有和 for a in nums1: for b in nums2: sum_map[a + b] += 1 # 在nums3和nums4中查找补数 for c in nums3: for d in nums4: target = - (c + d) count += sum_map.get(target, 0) return count

注意：这里使用defaultdict可以避免键不存在的判断，但普通字典的get方法也能实现同样效果。在实际面试中，解释清楚选择理由很重要。

2.4 复杂度分析与优化空间

时间复杂度：O(n^2)，因为我们进行了两次双重循环，每次都是n^2次操作。 空间复杂度：O(n^2)，最坏情况下nums1和nums2的所有和都不同。

进一步优化：如果某个数组有大量重复元素，可以考虑先统计元素频率再计算，但一般情况下上述解法已经足够。

3. 383.赎金信：字符频率统计

3.1 问题描述与简单解法

给定一个赎金信字符串和一个杂志字符串，判断赎金信是否能由杂志中的字符构成。杂志中的每个字符只能在赎金信中使用一次。

最直接的思路是用哈希表统计杂志中字符的频率，然后检查赎金信的字符是否都能满足。

3.2 实现细节与边界条件

def canConstruct(ransomNote, magazine): from collections import defaultdict mag_count = defaultdict(int) # 统计杂志字符频率 for c in magazine: mag_count[c] += 1 # 检查赎金信 for c in ransomNote: mag_count[c] -= 1 if mag_count[c] < 0: return False return True

提示：在Python中，可以使用Counter更简洁地实现，但手动实现能更好地展示理解深度。

3.3 空间优化与替代方案

如果字符集有限（如仅小写字母），可以用固定大小的数组代替哈希表：

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

这种方法空间复杂度为O(1)（固定26个位置），在实际应用中效率更高。

4. 15.三数之和：双指针经典应用

4.1 问题难点与暴力解法局限

给定整数数组nums，返回所有不重复的三元组[nums[i], nums[j], nums[k]]，使得i≠j≠k且nums[i]+nums[j]+nums[k]=0。

暴力三重循环的O(n^3)解法不仅效率低，还需要处理重复结果。我们需要更聪明的办法。

4.2 排序加双指针解法

关键步骤：

1. 对数组排序（O(nlogn)）
2. 固定一个数nums[i]，然后在i+1到末尾的区间内使用双指针寻找两数之和等于-nums[i]
3. 跳过重复元素以避免重复解

def threeSum(nums): nums.sort() res = [] n = len(nums) for i in range(n - 2): # 跳过重复的nums[i] if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, n - 1 target = -nums[i] while left < right: s = nums[left] + nums[right] if s == target: 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 elif s < target: left += 1 else: right -= 1 return res

4.3 复杂度分析与注意事项

时间复杂度：O(n^2) - 外层循环O(n)，内层双指针O(n) 空间复杂度：O(1)或O(n)（取决于排序实现）

关键细节：

1. 必须先排序数组
2. 需要仔细处理重复元素
3. 双指针移动时要注意边界条件

5. 18.四数之和：三数之和的扩展

5.1 问题升级与解法思路

在15题基础上，现在要求找出所有不重复的四元组，使得四数之和等于目标值（本题中目标值固定为0，但解法可推广）。

解法思路类似三数之和，增加一层循环：

1. 排序数组
2. 固定两个数nums[i]和nums[j]
3. 在j+1到末尾区间使用双指针寻找两数之和等于target-nums[i]-nums[j]

5.2 代码实现与剪枝优化

def fourSum(nums, target): nums.sort() res = [] n = len(nums) for i in range(n - 3): # 跳过重复的nums[i] if i > 0 and nums[i] == nums[i - 1]: continue # 剪枝：最小和已经大于target if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target: break # 剪枝：最大和仍然小于target if nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target: continue for j in range(i + 1, n - 2): # 跳过重复的nums[j] if j > i + 1 and nums[j] == nums[j - 1]: continue # 类似的剪枝优化 if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target: break if nums[i] + nums[j] + nums[n-2] + nums[n-1] < target: continue left, right = j + 1, n - 1 current_target = target - nums[i] - nums[j] while left < right: s = nums[left] + nums[right] if s == current_target: res.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 elif s < current_target: left += 1 else: right -= 1 return res

5.3 性能优化与边界处理

1. 添加了多级剪枝条件，提前终止不可能产生解的分支
2. 注意处理大整数溢出的情况（Python中不需要特别处理，但其他语言可能需要）
3. 时间复杂度O(n^3)，但通过剪枝在实际运行中可能接近O(n^2)

6. 算法技巧总结与实战建议

6.1 哈希表与双指针的选择

哈希表适合：

• 需要快速查找的场景
• 不要求顺序或位置关系
• 需要统计频率或存在性

双指针适合：

• 已排序数组
• 需要利用元素间大小关系
• 需要减少时间复杂度（如从O(n^2)降到O(n)）

6.2 处理重复元素的通用方法

1. 先排序数组
2. 在循环中检查当前元素是否与前一个相同
3. 找到解后跳过所有连续相同元素

6.3 面试中的常见错误

1. 忘记处理重复元素
2. 双指针移动逻辑错误（该移动左指针时移动了右指针）
3. 边界条件处理不当（如数组长度不足）
4. 过早优化（如在不必要时添加剪枝）

6.4 个人刷题心得

在实际刷题中，我发现这类问题有几个关键点：

1. 先写出暴力解法，再思考优化方向
2. 画图辅助理解双指针的移动逻辑
3. 对于重复元素处理，可以用小规模测试用例验证
4. 在面试中要边写边解释思考过程