算法打卡day5|哈希表篇01|Leetcode 242.有效的字母异位词 、19.删除链表的倒数第N个节点、202. 快乐数、1. 两数之和

哈希表基础知识

哈希表

哈希表关键码就是数组的索引下标，然后通过下标直接访问数组中的元素；数组就是哈希表的一种

一般哈希表都是用来快速判断一个元素是否出现集合里。例如要查询一个名字是否在班级里：

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)；

哈希函数

把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于 哈希表的大小了，此时为了保证映射出来的索引数值都落在哈希表上，会在再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上了。

但就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。这就造成了哈希碰撞

哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

拉链法

当小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了；（数据规模是dataSize， 哈希表的大小为tableSize）

线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：

常见的三种哈希结构

 在Java中，哈希结构是一种基于哈希表的数据结构，主要用于快速查找和存取数据。常见的哈希结构包括数组、集合和映射。以下是它们的定义、特性以及使用场景的介绍。

数组（Array）

定义：数组是一种线性数据结构，用于存储固定数量的同类型元素。它提供了通过索引快速访问元素的能力。
特性：数组的大小在创建时就已确定，且之后不能改变。数组在内存中连续分配空间，这有助于快速访问元素。
使用场景：当你需要快速随机访问元素，并且知道元素的数量时，数组是一个不错的选择。例如，处理固定大小的列表、缓冲区或矩阵。

集合（Collection)
 

定义：集合是Java集合框架的一部分，它提供了一组接口和类，用于存储和操作一组对象。集合框架包括List、Set等多种类型。

特性：集合框架提供了丰富的操作，如添加、删除、遍历元素等。集合可以动态增长和缩小，不需要预先指定大小。

使用场景：集合适用于存储和管理一组对象的场景，尤其是当对象的数量未知或可能变化时。例如，存储用户列表、日志消息或任何动态集合的数据。

映射（Map）

定义：映射是一种键值对的集合，它允许通过唯一的键快速检索值。Java中的Map接口及其实现类（如HashMap、TreeMap等）提供了这种功能。

特性：每个键最多映射到一个值，键不能重复。映射提供了快速的查找、插入和删除操作。

使用场景：映射适用于需要通过键来快速检索值的场景。例如，在数据库查询结果映射、实现属性文件解析、缓存数据等方面非常有用。

算法题

Leetcode   242.有效的字母异位词 

题目链接:242.有效的字母异位词 

大佬视频讲解：有效的字母异位词视频讲解

个人思路

利用哈希表结构，先遍历一遍a存字符数量到辅助数组，然后再遍历一遍b查值并删除对应字符数量，最后遍历一遍这个辅助数组，如果有字符数量不为0，则不为异位词。

解法

哈希数组

定义一个数组叫做help用来上记录字符串s里字符出现的次数。因为只包括小写字母，所以直接字符a映射为下标0，相应的字符z映射为下标25。再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，就能求出一个字母对应出现次数。 然后在遍历字符串t 的时候，对t中出现的字符映射哈希表索引上的数值做-1的操作。那么最后检查一下，help数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符。最后如果help数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

class Solution {public boolean isAnagram(String s, String t) {int[] help=new int[26];//辅助数组for(int i =0;i<s.length();i++){ // 求出字符串s对应字母的存在个数help[s.charAt(i) -'a'] ++;}for(int i =0;i<t.length();i++){help[t.charAt(i) -'a'] --;}for(int i=0;i<help.length;i++){ // help数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。if(help[i]!=0){return false;}}return true; // help数组所有元素都为零0，说明字符串s和t是字母异位词}
}

时间复杂度:O(nlog n)；（3个for循环）

空间复杂度:O(1);（没常量大小的辅助数组）

Leetcode 349. 两个数组的交集 

题目链接:349.两个数组之间的交集

大佬视频讲解：两个数组之间的交集视频讲解

个人思路

因为结果要求不重复，那可以用set集合；先用一个hashSet存取数组1的值，再看这个hashSet中是否包含数组2的值，如果包含则将数字放入结果集中；

解法

哈希集合

这道题目没有限制数值的大小，就无法使用数组来做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

但如果所有题目都直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。在数据量大的情况，差距是非常明显的。

class Solution {public int[] intersection(int[] nums1, int[] nums2) {//nums1 == null判断数组引用是否被初始化//nums1.length == 0 判断数组已经初始化后是否有元素if(nums1 == null || nums1.length == 0 || nums1 == null || nums1.length == 0 ){return new int[0];}Set<Integer>  setNum1=new HashSet<>();Set<Integer>  result=new HashSet<>();for(int i=0;i<nums1.length;i++){//遍历数组1存值setNum1.add(nums1[i]);}for(int num:nums2){ //遍历数组2的过程中判断哈希表中是否存在该元素if(setNum1.contains(num)){result.add(num);}}return result.stream().mapToInt(x -> x).toArray();//将结果集合转为数组}
}

//最后return的数组，也可以另外申请一个数组存放setRes中的元素int[] arr = new int[resSet.size()];int j = 0;for(int i : resSet){arr[j++] = i;}

时间复杂度:O(n)；（两个不嵌套的for循环）

空间复杂度:O(n);（使用多两个set）

Leetcode  202. 快乐数

题目链接:https://leetcode.cn/problems/happy-number/description/

个人思路

快乐数中一个很重要的定义，平方和就是不能重复，否则会无限循环；那可以使用hashSet来解决这道题。

解法

哈希集合

当遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

class Solution {public boolean isHappy(int n) {Set<Integer> res=new HashSet<>();//1本身就是快乐数//这个过程结果不能重复出现，不然会无限循环；while(n!=1 && !res.contains(n)){res.add(n);n=comput(n);//计算每个位置上的平方和}return n==1;}public int comput(int n){int sum=0;while(n>0){int temp= n%10;//求余数sum+=temp*temp;//累加平方和n=n/10;//从个位到十位到百位到...}return sum;}
}

时间复杂度:O( n)；（模内层循环comput，对于每个n，它会执行n次，因为它是对n的每一位数字进行平方然后求和）

空间复杂度:O(n);（ 在最坏的情况下，HashSet可能会存储所有小于等于n的数字，因此空间复杂度为O(n））

Leetcode 1. 两数之和 

题目链接:1. 两数之和 

 大佬视频讲解：两数之和 视频讲解

个人思路

因为既要求下标，又要求值，可以考虑使用哈希映射这个结构；

解法

哈希映射

在使用map时要明确两点：

1.map用来做什么

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

2.map中key和value分别表示什么

因为需要判断元素是否出现，还要真的元素的下标，所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

然后在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中；

class Solution {public int[] twoSum(int[] nums, int target) {int[] res=new int[2]; //nums == null判断数组引用是否被初始化//nums.length == 0 判断数组已经初始化后是否有元素if(nums==null || nums.length==0){return res;}Map<Integer,Integer> mapX=new HashMap<>();//key存数组值，value存数组下标for(int i=0;i<nums.length;i++){int temp=target-nums[i];if(mapX.containsKey(temp)){// 遍历当前元素，并在map中寻找是否有匹配的keyres[0]=i;res[1]=mapX.get(temp);break;}mapX.put(nums[i],i); // 如果没找到匹配对，就把访问过的元素和下标加入到map中}return res;}
}

时间复杂度:O(n)；（一个for循环）

空间复杂度:O(n);（使用map）

以上是个人的思考反思与总结，若只想根据系列题刷，参考卡哥的网址代码随想录算法官网