企业官网建设流程全解析

1. 四数相加 II问题解析

1.1 问题理解与思路分析

四数相加II问题要求我们统计四个数组中满足a+b+c+d=0的元组数量。直接暴力解法需要O(n⁴)的时间复杂度，显然不可取。更聪明的做法是将问题拆分为两个部分：

1. 先计算A和B数组中所有可能的a+b组合，用哈希表记录每种和出现的次数
2. 然后计算C和D数组中所有可能的c+d组合，查找哈希表中是否存在-(c+d)

这种分治策略将时间复杂度从O(n⁴)降低到O(n²)，是典型的空间换时间优化。

1.2 代码实现细节

class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int,int> map; int count=0; // 计算A+B的所有组合 for(int a:nums1){ for(int b:nums2){ map[a+b]++; } } // 计算C+D的所有组合并查找匹配 for(int c:nums3){ for(int d:nums4){ int target=0-(c+d); if(map.find(target)!=map.end()){ count+=map[target]; } } } return count; } };

注意：这里使用unordered_map而不是map，因为前者基于哈希表实现，查找时间复杂度为O(1)，而后者基于红黑树实现，查找时间复杂度为O(logn)。

1.3 复杂度分析与优化

• 时间复杂度：O(n²)，因为有两层嵌套循环，每层遍历n个元素
• 空间复杂度：O(n²)，最坏情况下A+B的所有组合都不相同

实际应用中，如果内存是瓶颈，可以考虑分批处理：先将A+B的结果存入哈希表，然后处理部分C+D组合后清除部分哈希表条目，但这会增加时间复杂度。

2. 赎金信问题解析

2.1 问题理解与思路分析

赎金信问题要求判断ransomNote字符串是否能由magazine字符串中的字符组成。核心要点：

1. magazine中的每个字符只能使用一次
2. ransomNote必须完全由magazine中的字符组成
3. 大小写敏感（本题中都是小写）

2.2 代码实现与优化

class Solution { public: bool canConstruct(string ransomNote, string magazine) { vector<int> record(26,0); // 快速失败：如果ransomNote比magazine长，直接返回false if(ransomNote.size()>magazine.size()){ return false; } // 统计magazine中各字符出现次数 for(int i=0;i<magazine.size();i++){ record[magazine[i]-'a']++; } // 检查ransomNote中的字符是否都能满足 for(int i=0;i<ransomNote.size();i++){ record[ransomNote[i]-'a']--; if(record[ransomNote[i]-'a']<0){ return false; } } return true; } };

2.3 复杂度分析与变种

• 时间复杂度：O(m+n)，其中m和n分别是magazine和ransomNote的长度
• 空间复杂度：O(1)，因为只使用了固定大小的数组（26个字母）

如果字符集更大（如包含Unicode字符），可以使用unordered_map代替固定数组，但会增加一些常数时间开销。

3. 三数之和问题解析

3.1 问题理解与思路分析

三数之和问题要求在数组中找到所有不重复的三元组，使得它们的和为0。这个问题的难点在于：

1. 需要避免重复的三元组
2. 需要高效地找到所有可能的组合

哈希表解法虽然可行，但去重逻辑较为复杂。更推荐使用双指针法：

1. 先对数组排序
2. 固定一个数nums[i]，然后在剩余部分使用双指针寻找nums[left]+nums[right]=-nums[i]
3. 通过跳过重复元素来避免重复解

3.2 哈希表解法代码

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int>> result; for(int a=0;a<nums.size();a++){ // 跳过重复的a if(a>0&&nums[a]==nums[a-1]){ continue; } unordered_set<int> set; for(int k=a+1;k<nums.size();k++){ // 复杂的去重逻辑 if(k>a+2&&nums[k]==nums[k-1]&&nums[k-1]==nums[k-2]){ continue; } int target=0-(nums[a]+nums[k]); if(set.find(target)!=set.end()){ result.push_back({nums[a],target,nums[k]}); set.erase(target); // 防止重复解 } else{ set.insert(nums[k]); } } } return result; } };

3.3 双指针解法（推荐）

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { if (nums[i] > 0) break; // 优化：第一个数大于0，后面不可能有解 if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重 int left = i + 1, right = nums.size() - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum < 0) left++; else if (sum > 0) right--; 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.1 问题理解与思路分析

四数之和是三数之和的扩展，要求在数组中找到所有不重复的四元组，使得它们的和等于目标值。解题思路：

1. 先对数组排序
2. 固定两个数nums[i]和nums[j]，然后在剩余部分使用双指针寻找nums[left]+nums[right]=target-nums[i]-nums[j]
3. 通过跳过重复元素来避免重复解

4.2 代码实现

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; if (nums.size() < 4) return result; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size() - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重 for (int j = i + 1; j < nums.size() - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 去重 int left = j + 1, right = nums.size() - 1; while (left < right) { long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; if (sum < target) left++; else if (sum > target) right--; else { result.push_back({nums[i], nums[j], 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.3 复杂度分析与优化

• 时间复杂度：O(n³)，外层两层循环，内层双指针
• 空间复杂度：O(1)或O(n)（取决于排序算法）

优化点：

1. 提前终止：如果nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target，可以提前终止
2. 跳过不可能的组合：如果nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target，可以跳过当前i

5. 总结与对比

5.1 四种问题的异同点

5.2 解题技巧总结

1. 哈希表是处理"查找互补元素"类问题的高效工具
2. 对于需要去重的问题，排序往往是必要的第一步
3. 双指针法在有序数组中可以有效降低时间复杂度
4. 分治思想（如将四数问题拆分为两数问题）可以显著提高效率
5. 提前终止和跳过不可能的组合是常见的优化手段

在实际编程面试中，理解这些问题的本质和掌握多种解法非常重要。特别是三数之和和四数之和问题，它们考察的不仅是编码能力，还有对算法优化的理解和实现细节的把控。