【算法训练营Day05】哈希表part1

哈希表理论基础

几个值得关注的知识点：

• hash表用于快速的判断元素是否存在（空间换时间）
• 其原理就是将数据通过散列函数映射到bucket中，如果发生hash碰撞，常见的处理方法有拉链法、线性探测法等等
• 在Java中几种常见的与hash表相关的数据结构：
  • 数组：判断、计数情况可使用
  • HashSet：存单个元素
  • LinkedHashSet：在HashSet的基础上增添了顺序性
  • HashMap：存键值对，线程不安全
  • LinkedHashMap：在hashmap的基础上增加了添加元素的顺序性
  • Hashtable：线程安全，一般不怎么用，使用ConcurrentHashMap替代

有效的字母异位词

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

解题逻辑：

• 要满足两个单词异位，换句话说就是要两个单词组成的字母以及字母的数量要一样。
• 我们可以遍历第一个字符串，将第一个字符串的所有字符加入到hashmap中，key使字母，value是字母的个数
• 对第二个字符串做同样的操作
• 比对两个hashmap
  • 长度首先要一样
  • 再比较每一项

代码如下：

class Solution {public boolean isAnagram(String s, String t) {char[] ss =  s.toCharArray();Map<Character,Integer> scount = new HashMap<>();for(char word : ss) {if(scount.containsKey(word)) {scount.put(word,scount.get(word) + 1);}else {scount.put(word,1);}}char[] tt =  t.toCharArray();Map<Character,Integer> tcount = new HashMap<>();for(char word : tt) {if(tcount.containsKey(word)) {tcount.put(word,tcount.get(word) + 1);}else {tcount.put(word,1);}}if(scount.size() != tcount.size()) return false;for(Map.Entry<Character, Integer> entry: scount.entrySet()) {Character key = entry.getKey();Integer value = entry.getValue();if(tcount.get(key) == null) return false;if(!tcount.get(key).equals(value)) return false;}return true;}
}

这种方法比暴力解法好一点点，但是也显得非常臃肿，原因就是实现hash表的数据结构并不是最优解。我们仔细观察这道题可以发现既然是英文单词，那么最多只有26个字母。那么我们可以将26个字母散列到长度为26的数组中，然后每个位置上对字母进行计数。

代码如下：

class Solution {public boolean isAnagram(String s, String t) {int[] record = new int[26];for (int i = 0; i < s.length(); i++) record[s.charAt(i) - 'a']++;for (int i = 0; i < t.length(); i++) record[t.charAt(i) - 'a']--;for (int count: record) if (count != 0) return false;return true; }    
}

这里我们可以思考一下将数组作为简单的hash表的注意点：

• 核心：将数组的索引作为key
• 使用场景
  • 能将要散列的属性与数组索引构成联系
  • key为密集分布的整数，并且范围小且已知（如果键稀疏则会造成大量的内存空间浪费，范围无法确定数组是不能动态扩容的）

两个数组的交集

题目链接：349. 两个数组的交集

最容易想到的就是将两个数组转化为set，然后直接取交集：

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = Arrays.stream(nums1).boxed().collect(Collectors.toSet());Set<Integer> set2 = Arrays.stream(nums2).boxed().collect(Collectors.toSet());set1.retainAll(set2);return set1.stream().mapToInt(Integer::intValue).toArray();}
}

答案是这么写的：

class Solution {public int[] intersection(int[] nums1, int[] nums2) {if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {return new int[0];}Set<Integer> set1 = new HashSet<>();Set<Integer> resSet = new HashSet<>();//遍历数组1for (int i : nums1) {set1.add(i);}//遍历数组2的过程中判断哈希表中是否存在该元素for (int i : nums2) {if (set1.contains(i)) {resSet.add(i);}}//方法1：将结果集合转为数组return resSet.stream().mapToInt(Integer::intValue).toArray();}
}

两种方法的时间复杂度是一样的都是O(n)，答案相当于只是把retainAll方法的逻辑展开了。如果还想优化效率，还是得依靠数组，因为本题限制了数组数据的范围，所以才考虑到可以使用这种方法：

class Solution {public int[] intersection(int[] nums1, int[] nums2) {int[] record1 = new int[1002];int[] record2 = new int[1002];for(int num : nums1) record1[num] += 1;for(int num : nums2) record2[num] += 1;List<Integer> resultList = new ArrayList<>();for(int i = 0;i < 1002;i++) if(record1[i] > 0 && record2[i] > 0) resultList.add(i);return resultList.stream().mapToInt(Integer::intValue).toArray();}
}

快乐数

题目链接：202. 快乐数

解题逻辑：

本题直接按照题目的步骤写代码即可，但是要弄明白，每一个数字在执行的过程中只可能有两种结果：

• 无限循环，返回false
• 满足快乐数要求，返回true

既然无限循环返回false，那么我们就可以将结果进行一个记录，有重复直接返回false

代码如下：

class Solution {public boolean isHappy(int n) {int sum = n;Set<Integer> record = new HashSet<>();while(sum != 1) {int num = sum;sum = 0;while(num >= 1){int temp = num % 10;sum += temp * temp;num /= 10;}if(record.contains(sum)) return false;record.add(sum);}return true}
}

两数之和

题目链接：1. 两数之和

首先暴力解法很容易想到，这种方法的时间复杂度是N方：

class Solution {public int[] twoSum(int[] nums, int target) {for(int i = 0;i < nums.length;i++) {for(int j = i + 1;j < nums.length;j++) {if(nums[i] + nums[j] == target) return new int[]{i,j};}}return null;}
}

如果要继续优化，我们就要想办法使用单层循环解决问题，一开始我想到遍历数组，把每个元素塞到hashmap中，key是数组元素，value该元素在数组中的索引，然后再次遍历数组，在map中寻找target - 遍历元素。但是这样的话无法处理target是两个相同元素的加和，因为hashmap的key是不可能重复的。既然这样的话那么我们就只能一边遍历数组，一边添加到hashmap中。

解题逻辑如下：

• 初始化一个hashmap用以存储已经存在的其中一个加数
• 遍历数组，在hashmap中寻找target - 遍历元素是否存在
  • 如果存在，通过key查找value结合当前遍历索引返回答案
  • 如果不存在，把该值添加到hashmap中，表示这个加数存在，可供后续使用

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> records = new HashMap<>();for(int i = 0;i < nums.length;i++) {int need = target - nums[i];if(records.get(need) == null) records.put(nums[i],i);else return new int[]{i,records.get(need)};}return null;}
}