【leetcode速通java版】04——哈希表

前 言
🍉 作者简介：半旧518，长跑型选手，立志坚持写10年博客，专注于java后端
☕专栏简介：代码随想录leetcode速通训练营java版本
🌰 文章简介：哈希表理论，leetcodeT242,T349,T202,T1

一、哈希表的基础理论回顾

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)双指针适用于两个数组/集合等情况，可以一轮遍历搞定问题。