【leetcode速通java版】04——哈希表
【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)双指针适用于两个数组/集合等情况，可以一轮遍历搞定问题。
腾讯云开发者
