wordpress视频网站用什么播放器,深圳市绿色建筑信息平台,软件技术专升本对口专业,网站品牌形象设计怎么做哈希表 理论知识#xff08;本文来自于代码随想录摘抄#xff09;什么是哈希常见的三种哈希结数组#xff1a;set:map:其他常用方法或者技巧#xff08;自己总结的#xff09; 练习题和讲解有效的字母移位词349. 两个数组的交集1. 两数之和454. 四数相加 II15. 三数之和 总… 哈希表 理论知识本文来自于代码随想录摘抄什么是哈希常见的三种哈希结数组set:map:其他常用方法或者技巧自己总结的 练习题和讲解有效的字母移位词349. 两个数组的交集1. 两数之和454. 四数相加 II15. 三数之和 总结 理论知识本文来自于代码随想录摘抄
什么是哈希
哈希表中关键码就是数组的索引下标然后通过下标直接访问数组中的元素如下图所示 那么哈希表能解决什么问题呢一般哈希表都是用来快速判断一个元素是否出现集合里。
常见的三种哈希结
当我们想使用哈希法来解决问题的时候我们一般会选择如下三种数据结构。 数组 set 集合 map(映射)
数组
当目标的范围是已知的是小的我们会使用数组。经常使用所以少介绍。
set: map: 其他常用方法或者技巧自己总结的 10用来判断某个值是否存在哈希表中containsKey()
if(result.containsKey(temp)){}练习题和讲解
有效的字母移位词
使用int 前置知识 字母a-z,A-Z的ASCII码是连续的。 所以’a’-‘a’0‘z’-‘a’25
class Solution {public boolean isAnagram(String s, String t) {int[] arrnew int[26]; //用来存储26个字母出现的次数for(int i0;is.length();i){ //字符串用length()方法数组为length。因为对于字符串length是方法数组是内置属性。 arr[s.charAt(i)-a]; //charAt(i)获取字符串中i位置的字符。 我们在对于的下标的位置1.比如出现z则是z-a,在25这个位置1.};for(int i0;it.length();i){arr[t.charAt(i)-a]--; //目的同样在对应位置-1抵消s字符串中出现的字母。};for(int a:arr){ //增强for循环方法。if(a!0){ //进行判断如果不等0证明两个里面的出现字母的数量不一致。return false;}}return true;}
}349. 两个数组的交集
349. 两个数组的交集 使用set
class Solution {public int[] intersection(int[] nums1, int[] nums2) {if (nums1 null || nums1.length 0 || nums2 null || nums2.length 0) {return new int[0];} //首先判断是否为空SetInteger set1 new HashSet(); //使用set可以直接去重SetInteger resSet new HashSet();//遍历数组1for (int i : nums1) {set1.add(i); }//遍历数组2的过程中判断哈希表中是否存在该元素for (int i : nums2) {if (set1.contains(i)) { //contains() 判断这个值是否在哈希表中resSet.add(i);}}//另外申请一个数组存放setRes中的元素,最后返回数组int[] arr new int[resSet.size()];int j 0;for(int i : resSet){arr[j] i;}return arr;}
}1. 两数之和
1. 两数之和 使用map需要存放 key value
class Solution {public int[] twoSum(int[] nums, int target) {// 创建一个 HashMap 来存储数字及其对应的索引MapInteger, Integer map new HashMap();int n nums.length;// 遍历数组for (int i 0; i n; i) {// 计算当前元素的补数int temp target - nums[i];// 检查补数是否在 HashMap 中if (map.containsKey(temp)) {// 找到结果那么返回当前索引和补数的索引return new int[]{map.get(temp), i};}// 如果没有找到补数就把当前数字和它的索引放入 HashMapmap.put(nums[i], i);}// 如果没有找到返回一个空数组考虑到题目保证有解这里可以省略return new int[]{};}
}454. 四数相加 II
454. 四数相加 II
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res 0;//不仅要保存值还需要保存其出现次数所以使用map(key,value)来进行存储数据。MapInteger, Integer map new HashMapInteger, Integer();//统计两个数组中的元素之和同时统计出现的次数放入mapfor (int i : nums1) {for (int j : nums2) {int sum i j;map.put(sum, map.getOrDefault(sum, 0) 1);//getOrDefault这个的意思是如果存在返回存在的值不存在返回default0}}//统计剩余的两个元素的和在map中找是否存在相加为0的情况同时记录次数for (int i : nums3) {for (int j : nums4) {//因为本题不去重所以有不同组合需要统计的值为 ressum(对应的值);res map.getOrDefault(0 - i - j, 0);}}return res;}
}15. 三数之和
15. 三数之和
使用哈希集合
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length; i) {// 如果第一个元素大于零不可能凑成三元组if (nums[i] 0) {return result;}// 三元组元素a去重if (i 0 nums[i] nums[i - 1]) {continue;}HashSetInteger set new HashSet();for (int j i 1; j nums.length; j) {// 三元组元素b去重if (j i 2 nums[j] nums[j - 1] nums[j - 1] nums[j - 2]) {continue;}int c -nums[i] - nums[j];if (set.contains(c)) {result.add(Arrays.asList(nums[i], nums[j], c));set.remove(c); // 三元组元素c去重} else {set.add(nums[j]);}}}return result;}
}使用双指针更为推荐
class Solution {public ListListInteger threeSum(int[] nums) {//二维集合因为不止一个集合ListListInteger ansnew ArrayList();int lennums.length;//如果值小于3则没有意义if(len3||numsnull) return ans;//排序更方便我们双指针的移动Arrays.sort(nums);//定i的位置然后动left和right两个指针的位置来凑0for(int i0;ilen;i){//如果第一个i都0则不可能三数之和为0if(nums[i]0) break;//题目去重所以我们判断前一位值如果等于后一位则跳过。if(i0nums[i]nums[i-1]) continue;//定义左右指针 int Li1;int Rlen-1; while(LR){int sum nums[i]nums[R]nums[L];//如果相等则添加进入二维数组中if(sum0){ans.add(Arrays.asList(nums[i],nums[L],nums[R]));//归零while(LR nums[L]nums[L1]) L;while(LR nums[R]nums[R-1]) R--;L;R--;}//和小就左指针右移和大就右指针左移else if(sum0)L;else if(sum0)R--;}}//返回二维数组。return ans;}
}总结
哈希表理论基础 在关于哈希表你该了解这些 (opens new window)中我们介绍了哈希表的基础理论知识不同于枯燥的讲解这里介绍了都是对刷题有帮助的理论知识点。
一般来说哈希表都是用来快速判断一个元素是否出现集合里。
对于哈希表要知道哈希函数和哈希碰撞在哈希表中的作用。
哈希函数是把传入的key映射到符号表的索引上。
哈希碰撞处理有多个key映射到相同索引上时的情景处理碰撞的普遍方式是拉链法和线性探测法。
接下来是常见的三种哈希结构
数组 set集合 map映射 在C语言中set 和 map 都分别提供了三种数据结构每种数据结构的底层实现和用途都有所不同在关于哈希表你该了解这些 (opens new window)中我给出了详细分析这一知识点很重要
例如什么时候用std::set什么时候用std::multiset什么时候用std::unordered_set都是很有考究的。
只有对这些数据结构的底层实现很熟悉才能灵活使用否则很容易写出效率低下的程序。
