算法day06-哈希表篇（2）
目录[*]四数相加II
[*]赎金信
[*]三数之和
[*]四数之和
一、四数相加II
454. 四数相加 II - 力扣（LeetCode）
主要思路：
[*]分组+哈希表优化：
[*]将四个数组分成两组，nums1 和 nums2 为一组，nums3 和 nums4 为另一组。
[*]首先计算 nums1 和 nums2 中所有可能的元素对的和，并用哈希表记录每个和出现的次数。
[*]然后计算 nums3 和 nums4 中所有可能的元素对的和的相反数（即 -(nums3 + nums4)），并在哈希表中查找该值是否存在。如果存在，说明存在对应的 nums1 + nums2 使得总和为 0，此时将哈希表中的计数累加到结果中。
[*]复杂度分析：
[*]时间复杂度：O(N²)，其中 N 是数组的长度。我们需要遍历 nums1 和 nums2 的所有组合（O(N²)），以及 nums3 和 nums4 的所有组合（O(N²)），哈希表的插入和查询操作均为 O(1)。
[*]空间复杂度：O(N²)，哈希表最多存储 N² 个不同的和。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int n = nums1.length;
Map<Integer, Integer> map = new HashMap<>();
for(int n1 : nums1){ //先把1和2组中的和存储到map中
for(int n2 : nums2){
int sum = n1+n2;
map.put(sum, map.getOrDefault(sum,0)+1);
}
}
int count = 0;
for(int n1: nums3){ //看3和4组的和是否在map中出现过，出现过几次
for(int n2: nums4){
int target = - n1 - n2;
if(map.containsKey(target)){
count += map.get(target);
}
}
}
return count;
}
}//时间复杂度：O(N^2)
//空间复杂度：O(N^2)二、赎金信
383. 赎金信 - 力扣（LeetCode）
该代码用于判断 ransomNote 是否能由 magazine 中的字符构成（每个字符只能用一次）。思路是：
[*]统计 magazine 的字符频率（用 HashMap 存储）。
[*]遍历 ransomNote 的字符，检查是否在 magazine 中有足够的字符可用：
[*]如果某个字符不存在或数量不足，返回 false。
[*]否则，减少该字符的剩余可用数量。
[*]如果全部字符都能匹配，返回 true。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
char[] cc = magazine.toCharArray();
Map<Character,Integer> map = new HashMap<>();
for(char c : cc){
map.put(c, map.getOrDefault(c,0)+1); //记录每个字符出现的次数
}
for(char c : ransomNote.toCharArray()){
if(!map.containsKey(c)){
return false;
}else{ //若r中出现的字符在m中出现过
map.put(c, map.getOrDefault(c,0)-1); //每出现一次就消耗一次
if(map.getOrDefault(c,0)<0){
return false;
}
}
}
return true;
}
}
//时间复杂度：O(N+M)
//空间复杂度：O(M)(可以优化成O(1))四、四数之和
地址：https://leetcode.cn/problems/4sum/
主要思路：这道题可以用dfs来做，依次对每个数选或不选，就可以选到所有的情况。但这里有一个问题是，选出的path之间不能重复（顺序不同但数字一样也看成重复）。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // 排序
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums == nums) {
continue; // 跳过重复元素
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums + nums + nums;
if (sum == 0) {
result.add(Arrays.asList(nums, nums, nums));
// 跳过重复元素
while (left < right && nums == nums) left++;
while (left < right && nums == nums) right--;
left++;
right--;
} else if (sum < 0) {
left++; // 需要更大的数
} else {
right--; // 需要更小的数
}
}
}
return result;
}
}
总结
这篇博客主要是对几道经典的“和类问题”进行梳理，包括四数相加 II、赎金信、三数之和、四数之和。虽然每道题具体做法不同，但其实背后的解题思路是相通的。
像四数相加 II 是典型的“分组 + 哈希优化”，思路比较巧，通过先处理前两个数组的所有组合和，再查找后两个数组对应的反向值，能大大减少时间复杂度。赎金信用的是最基础的哈希计数思想，但也是很多字符串题的基础套路，属于必掌握的部分。
三数之和和四数之和这两个题就更有代表性了，用排序+双指针或者 DFS+剪枝去重的方式，不仅能解决这类和为目标的组合问题，也能迁移到很多其他类似题上。尤其三数之和是很适合练习双指针写法和去重逻辑的。
总的来说，刷这几题对我帮助挺大，尤其是在理解“组合类问题怎么拆解”、“怎么控制重复解”、“怎么用哈希表提升效率”等方面，希望这篇总结也能对你有点启发。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]