一、哈希表的基础理论回顾
1.哈希表主要用来解决快速获取某个元素的问题。比如查找一个学校的姓名为张三的学生，如果用数组需要的时间复杂度为O(n),但是使用哈希表的时间复杂度为O(1).
2.哈希冲突是指经过哈希计算后，其存储位置在数组的同一个物理空间。一般哈希冲突有两种解决思路：(1)拉链法 (2)线性探测法。 如果使用拉链法，需要特别注意数组的长度，避免空值过多浪费空间，也需要避免因为拉链过长导致查找元素的时间代价过高。 使用线性探测法，必须保证数组大小大于需要存储的元素大小。
二、真题特训
leetcode T242 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
说明: 你可以假设字符串只包含小写字母。
解法1：排序
题中问题等价于：将两个字符串排序后相等。
class Solution { public boolean isAnagram(String s, String t) { // 题解1：排序后字符串相等 // 1. 判断长度是否相等 if(s.length() != t.length()) return false; // 2.转换成字符串数组 char [] sArr= s.toCharArray(); char [] tArr= t.toCharArray(); // 3.排序 Arrays.sort(sArr); Arrays.sort(tArr); // 4.比较 return Arrays.equals(sArr, tArr); } }
总结：相等是线索，进行排序把问题转换为相等问题。将问题转换为熟悉的问题处理。
复杂度分析：
- 时间复杂度：
方法二：哈希表
字母只有26个，维护一个字母频次的哈希表记录，再遍历字符串t，每出现一个字母就将频次减少1，如果有＜0的频次，就说明出现了不一样的字符。
class Solution { public boolean isAnagram(String s, String t) { // 题解2：哈希表 // 0. 字符串比较基操，判断长度 if(s.length() != t.length()) return false; // 1.构造频次哈希表 int [] table = new int[26]; // 2.记录字符串s的字母频次 for(int i = 0; i < s.length(); i++) { table[s.charAt(i) - 'a']++; } // 3.遍历t，判断进行递减操作 for(int j = 0; j < t.length(); j++) { int num = --table[t.charAt(j) - 'a']; if(num < 0) return false; } return true; } }
总结：字母数量【有限】是第二个线索，可以利用哈希表解决问题。
leetcodeT349 两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
解法1：利用好集合
class Solution { public int[] intersection(int[] nums1, int[] nums2) { // 解法1 两个集合：维护两个集合，比较集合得元素是否重叠即可。 Set<Integer> set1 = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<Integer>(); for(int num : nums1) { set1.add(num); } for(int num : nums2) { set2.add(num); } return getIntersection(set1, set2); } int[] getIntersection(Set<Integer> set1, Set<Integer> set2) { // 默认set2大,最大程度压榨性能 if (set1.size() > set2.size()) { return getIntersection(set2, set1); } Set<Integer> intersectionSet = new HashSet<Integer>(); for(int num : set1) { if(set2.contains(num)) { intersectionSet.add(num); } } int[] result = new int[intersectionSet.size()]; int i = 0; for(int num : intersectionSet) { result[i++] = num; } return result; } }
方法二：排序 + 双指针
如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
class Solution { public int[] intersection(int[] nums1, int[] nums2) { // 排序 Arrays.sort(nums1); Arrays.sort(nums2); int length1 = nums1.length, length2 = nums2.length; int[] intersection = new int[length1 + length2]; int index = 0, index1 = 0, index2 = 0; while (index1 < length1 && index2 < length2) { int num1 = nums1[index1], num2 = nums2[index2]; if (num1 == num2) { // 保证加入元素的唯一性 if (index == 0 || num1 != intersection[index - 1]) { intersection[index++] = num1; } index1++; index2++; } else if (num1 < num2) { index1++; } else { index2++; } } return Arrays.copyOfRange(intersection, 0, index); } }
总结：
(1)排序是个常用中间方法。
(2)双指针适用于两个数组/集合等情况，可以一轮遍历搞定问题。
