文章目录

• • 难点
• LeetCode454 四数相加II
• • 题目
  • AC代码
• LeetCode15三数之和
• • 题目
  • 去重逻辑的思考
  • • a的去重
    • b 与c的去重
  • AC代码
• LeetCode18 四数之和
• • 题目
  • • 剪枝
  • AC代码
• 哈希表总结
• • • 数组
    • set（集合）
    • map（映射）
  • 收获
• 黑暗就是你的蜡烛，你的边界就是你追寻的起点

难点

• 为什么使用哈希法
• 为什么使用map结构，而不是数组和set
• key用来存储什么，value用来存储什么

LeetCode454 四数相加II

题目

AC代码

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {// 生成 temp 存放1+2 2+3int temp;//  生成res 用于存储 nums1 出现次数int res =0;//生成mapMap  map= new HashMap<>();//进行循环遍历for(int i: nums1){for(int j:nums2){temp = i+j;if(map.containsKey(temp)){map.put(temp,map.get(temp)+1);}else{map.put(temp,1);}}}//a+b 如果包含 怎么 else 怎么样//c+d for(int i:nums3){for(int j:nums4){temp=i+j;if(map.containsKey(0-temp)){res +=map.get(0-temp);}}}return res;}
}

LeetCode15三数之和

题目

去重逻辑的思考

a的去重

说道去重，其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]
a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。
重点在于用 nums[i]== nums[i+1] 还是nums[i]==nums[i-1] 前者的话 是在三个数中 a,b,c 中不能去重复值
可是 1，1，2 是可以的 所以 所以前者不并不适用
我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的
那么应该这么写

if (i > 0 && nums[i] == nums[i - 1]) {continue;
}

b 与c的去重

就涉及到了去重的逻辑上要添加上对left和right的去重

while (left < right && nums[right] == nums[right + 1]) right--;while (left < right && nums[left] == nums[left - 1]) left++;

AC代码

class Solution {public List> threeSum(int[] nums) {// 初始化 一个多维数组 resultList> result =new ArrayList<>(); //进行排序Arrays.sort(nums);// for循环 for(int i=0;i//合理性判定 ,将A去重if(nums[i]>0){return result;}if(i>0&& nums[i]==nums[i-1]){continue;}//左右初始化int left= i+1;int right=nums.length-1;//while(right>left) while(right>left){int sum =nums[i]+nums[left]+nums[right];if(sum >0){right--;}else if(sum<0){left++;}         // int sum// 将 bc 去重else{result.add(Arrays.asList(nums[i], nums[left], nums[right]));//将三元组加入result之后while(right>left&& nums[left]==nums[left+1]) left++;while(right>left&& nums[right] == nums[right-1])right--; left++;right--;}        //return result}}return result;}
}

LeetCode18 四数之和

题目

剪枝

就是通过某种判断，避免一些不必要的遍历过程

AC代码

相较于三数之和 原理差不多   只不过多加了一个数字的循环
class Solution {public List> fourSum(int[] nums, int target) {List> result = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {// nums[i] > target 直接返回, 剪枝操作if (nums[i] > 0 && nums[i] > target) {return result;}if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重continue;}for (int j = i + 1; j < nums.length; j++) {if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重continue;}int left = j + 1;int right = nums.length - 1;while (right > left) {// nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum > target) {right--;} else if (sum < target) {left++;} else {result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));// 对nums[left]和nums[right]去重while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;left++;right--;}}}}return result;}
}

哈希表总结

对于哈希表，要知道哈希函数和哈希碰撞在哈希表中的作用

• 哈希函数 是把传入的key映射到符号表的索引上。
• 哈希碰撞 处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。
• 接下来常见的三种哈希结构

数组

在242.有效的字母异位词 (opens new window)中，就用到了数组，提到数组就是简单的哈希表，
这道题包括小写字母用数组最合适
相对于map 结构来说 ，map消耗空间比数组大的 而题目中要求有小写字母 也相当于是对我们的暗示要用到数组

set（集合）

在349. 两个数组的交集 (opens new window)中我们给出了什么时候用数组就不行了，需要用set。

这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

map（映射）

在1.两数之和 (opens new window)中map正式登场。

来说一说：使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和
y的下标。所以set 也不能用。 map是一种 value>的结构，本题可以用key保存数值，用value在保存数值所在的下标。所以使用map最为合适。

收获

黑暗就是你的蜡烛，你的边界就是你追寻的起点