算法day06-哈希表篇（2）

荪俗 · 昨天 18:25

四数相加II
赎金信
三数之和
四数之和

一、四数相加II

454. 四数相加 II - 力扣（LeetCode）

　　主要思路：

分组+哈希表优化：
- 将四个数组分成两组，nums1 和 nums2 为一组，nums3 和 nums4 为另一组。
- 首先计算 nums1 和 nums2 中所有可能的元素对的和，并用哈希表记录每个和出现的次数。
- 然后计算 nums3 和 nums4 中所有可能的元素对的和的相反数（即 -(nums3[k] + nums4[l])），并在哈希表中查找该值是否存在。如果存在，说明存在对应的 nums1 + nums2[j] 使得总和为 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[i] == nums[i - 1]) {
            continue; // 跳过重复元素
         }

         int left = i + 1;
         int right = nums.length - 1;

         while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                  result.add(Arrays.asList(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--;
            } else if (sum < 0) {
                  left++; // 需要更大的数
            } else {
                  right--; // 需要更小的数
            }
         }
      }

      return result;
}
}
复制代码

总结

　　这篇博客主要是对几道经典的“和类问题”进行梳理，包括四数相加 II、赎金信、三数之和、四数之和。虽然每道题具体做法不同，但其实背后的解题思路是相通的。
像四数相加 II 是典型的“分组 + 哈希优化”，思路比较巧，通过先处理前两个数组的所有组合和，再查找后两个数组对应的反向值，能大大减少时间复杂度。赎金信用的是最基础的哈希计数思想，但也是很多字符串题的基础套路，属于必掌握的部分。
　　三数之和和四数之和这两个题就更有代表性了，用排序+双指针或者 DFS+剪枝去重的方式，不仅能解决这类和为目标的组合问题，也能迁移到很多其他类似题上。尤其三数之和是很适合练习双指针写法和去重逻辑的。
　　总的来说，刷这几题对我帮助挺大，尤其是在理解“组合类问题怎么拆解”、“怎么控制重复解”、“怎么用哈希表提升效率”等方面，希望这篇总结也能对你有点启发。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

算法day06-哈希表篇（2）

浏览过的版块

签约作者