算法训练营day07 哈希表（拆分、统计、逻辑判断）综合运用

💡 解题思路

1. 📝 确定输入与输出
2. 🔍 分析复杂度
3. 🔨 复杂题目拆分 ：严谨且完整 地拆分为更小的子问题（哈希表的使用场景）–（多总结）
4. 💭 选择处理逻辑： 根据拆分后的子问题，总结并选择合适的问题处理思路
5. 🔎 检查特殊情况：边界条件和特殊情况
6. 🏁 返回结果

---

● 454.四数相加II
（拆分思想）

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {HashMap<Integer, Integer> map = new HashMap<>();int len = nums4.length;for (int value : nums4) {for ( int value1 : nums3) {map.put(value + value1,map.getOrDefault(value1 + value, 0)+1);}}int count = 0;for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {int sum = nums1[i] + nums2[j];count += map.getOrDefault(-sum, 0);}}return count;}
}

● 383. 赎金信
（存储统计）

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] nums = new int[26];int len = magazine.length();for (int i = 0; i < len; i++) {nums[magazine.charAt(i)-'a']++;}int len1 = ransomNote.length();for (int i = 0; i < len1; i++) {int c = ransomNote.charAt(i)-'a';nums[c]--;if (nums[c] < 0) return false;}return true;}
}

● 15. 三数之和 （存储统计+逻辑判断）

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();int len = nums.length;if (len < 3) return res;Arrays.sort(nums); // 有序保证，i != j != kfor (int i = 0; i < len - 2; i++) {if (nums[i] > 0) break;if (i > 0 && nums[i] == nums[i-1]) continue;int left = i + 1, right = len - 1, target = nums[i];while (left < right) {target = nums[i] + nums[left] + nums[right];if (target == 0) {res.add(Arrays.asList(nums[i], nums[left], nums[right]));left++;right--;while(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;} else if (target < 0) left++;else right--;  }}return res;}
}

● 18. 四数之和 （拆分+三数之和）

class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> fourSum(int[] nums, int target) {if (nums == null || nums.length <= 3) return res; int len = nums.length;Arrays.sort(nums);for (int i = 0; i < len - 3; i++) {if (i > 0 && nums[i] == nums[i-1]) continue;// 减枝if ((long) nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;if ((long) nums[i] + nums[len-1] + nums[len-2] + nums[len-3] < target) continue;threeSum(i, nums, target-nums[i]);}return res;}private void threeSum(int index, int[] nums, int target) {int len = nums.length;for (int i = index + 1; i < len - 2; i++) {if (i > index + 1 && nums[i] == nums[i-1]) continue;// 剪枝if ((long) nums[i] + nums[i+1] + nums[i+2] > target) break;if ((long) nums[i] + nums[len-1] + nums[len-2] < target) continue;int left = i+1, right = len - 1;while(left < right) {if (nums[left] + nums[right] + nums[i] == target) {res.add(Arrays.asList(nums[index], nums[i], nums[left], nums[right]));left++;right--;// 去重while(left < right && nums[left] == nums[left-1]) left++;while(left < right && nums[right] == nums[right+1]) right--;}// 缩小范围while(left < right && nums[left] + nums[right] + nums[i] > target) {right--;}while(left < right && nums[left] + nums[right] + nums[i] < target) {left++;}}}}
}