代码随想录day06，哈希表part1

哈希表理论基础

哈希表是根据关键码的值而直接进行访问的数据结构。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。一般哈希表都是用来快速判断一个元素是否出现集合里。

通过哈希函数把数组中的数字直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道数字位置。

哈希函数一般是通过特定编码方式，可以将其他数据格式转化为不同的数值。比如说想要把[123456]，如果将每个数字减1，就可以将他们映射到另一个数组[012345]，另一个数组上的位置就是他们的索引。

但是可能会发生哈希碰撞，比如，两个数字都映射到了1，那就会发生碰撞。一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

拉链法

拉链法就是，如果在索引1发生碰撞，那就是说有两个元素都映射到了1，那就在1这个位置存储在链表上。拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

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

就是小李小王都映射到了1，上面是横着用链表把他俩都放下，这个就是竖着把他俩都放下。例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set （集合）
• map(映射)

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

242.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

字母异位词就是排列，相当于，输入一个串 S，一个串 T，判断T是不是S中的一种排列

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

数组大小为26的record数组，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。

用这个record数组来记录字符串s里字符出现的次数，s 里出现的字母 +1，t 里出现的字母 −1，最后 26 个槽全为 0 才能说明是字母异位词。

s和t字符出现的次数一样，那么他们两个肯定是同样的字符进行不同排列的字符串。如果不一样，那连字符都不一样，更不用说是相同字符的不同排列了。

class Solution{ public boolean isAnagram(String s, String t) { int[] record = new int[26]; for(int i=0;i<s.length();i++){ //统计s字符出现次数 //s.charAt(i)：从字符串s中取出第i个字符 //并不需要记住字符a的ASCII，只要求出一个相对数值就可以了 // record[... ]++：对映射后的索引位置的值做加 1操作 record[s.charAt(i) - 'a']++; } //统计t字符出现字符, for(int i = 0;i<t.length();i++){ record[t.charAt(i) - 'a']--; } for(int count:record){ if(count !=0){ return false; } } return true; } } 

349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

 输入：nums1 = [1,2,2,1], nums2 = [2,2]  输出：[2]

输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序。

这个题增添了数值范围：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

题目限制了数值大小，所以可以采用数组求解。

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

但是不能什么哈希问题都用set，因为直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

使用数组求解：

class Solution{ public int[] intersection(int[] nums1, int[] nums2) { //1002是因为比最大元素值1000多2，预留冗余避免越界 int[] hash1 = new int[1002]; int[] hash2 = new int[1002]; //遍历数组nums1的每一个元素，计数在nums1 中出现的次数 for(int i:nums1) hash1[i]++; for(int i:nums2) hash2[i]++; //创建动态整数列表,收集两个数组的交集元素 List<Integer> resList = new ArrayList<>(); for(int i=0;i<1002;i++){ //交集元素+1 if(hash1[i]>0&&hash2[i]>0) resList.add(i); } //将存储交集元素的 List 集合（resList），转换为最终需要返回的 int 类型数组 int res[] = new int[resList.size()]; for(int j = 0; j < resList.size(); j++){ res[j] = resList.get(j); } return res; } }

写法2：用 HashSet 去重，再 retainAll 取交集，不受数据范围限制

class Solution { public int[] intersection(int[] nums1, int[] nums2) { //注意和上面对比，遍历的逻辑一样，只是换成set Set<Integer> set1 = new HashSet<>(); Set<Integer> set2 = new HashSet<>(); for (int n : nums1) set1.add(n); for (int n : nums2) set2.add(n); //保留 set1 中与 set2 共有的元素，删除 set1 中独有的元素 set1.retainAll(set2); // 取交集 //创建结果数组 int[] res = new int[set1.size()]; //遍历 set1 中的交集元素，通过一个计数变量 i 把元素依次存入 res 数组 int i = 0; for (int n : set1) res[i++] = n; return res; } }

第202题. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19。输出：true 解释： 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

class Solution{ public boolean isHappy(int n){ Set<Integer> record = new HashSet<>(); //如果当前数n已存在于record（存储过的中间结果），说明进入无限循环（永远到不了1），终止循环 while(n!=1 &&!record.contains(n)){ record.add(n); n = getNextNumber(n); } return n==1; } private int getNextNumber(int n) { int res = 0; //计算一个整数 n 所有位上数字的平方和 while(n>0){ int temp = n%10;//个位 res +=temp*temp;//个位平方和 n=n/10;//去掉个位，接下来循环算十位，直到变成0 } return res; } }

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例 ：

 输入：nums = [2,7,11,15], target = 9  输出：[0,1]  解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题，不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

遍历当前元素，并在map中寻找是否有匹配的key，计算互补元素temp，判断哈希表map中是否存在互补元素temp，存在就找到了答案。将当前元素的下标i存入res的第二个位置，获取互补元素temp在数组中的下标，并存入res的第一个位置。

res[1]存储后遍历到的元素的下标（即 i），因为 i是当前循环的索引，比哈希表中存储的 j（map.get(temp)）更大。

//使用哈希表 public int[] twoSum(int[] nums, int target) { int[] res = new int[2];//结果数组 if(nums == null || nums.length == 0){ return res; } Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){ // 遍历当前元素，并在map中寻找是否有匹配的key //计算互补元素temp int temp = target - nums[i]; //判断哈希表map中是否存在互补元素temp，存在就找到了答案 if(map.containsKey(temp)){ //将当前元素的下标i存入res的第二个位置 res[1] = i; //获取互补元素temp在数组中的下标，并存入res的第一个位置; res[0] = map.get(temp); break; } // 如果没找到匹配对，就把访问过的元素和下标加入到map中 map.put(nums[i], i); } return res; }

如果题目没保证有序，就不能用双指针。如果想用双指针需要先排序，数组有序，就应该想到双指针技巧。