Hash表算法
哈希表
- 理论知识(本文来自于代码随想录摘抄)
- 什么是哈希
- 常见的三种哈希结
- 数组:
- set:
- map:
- 其他常用方法或者技巧(自己总结的)
- 练习题和讲解
- 有效的字母移位词
- 349. 两个数组的交集
- 1. 两数之和
- 454. 四数相加 II
- 15. 三数之和
- 总结
理论知识(本文来自于代码随想录摘抄)
什么是哈希
哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素,如下图所示:
那么哈希表能解决什么问题呢,一般哈希表都是用来快速判断一个元素是否出现集合里。
常见的三种哈希结
当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。
数组
set (集合)
map(映射)
数组:
当目标的范围是已知的,是小的,我们会使用数组。(经常使用,所以少介绍。)
set:
map:
其他常用方法或者技巧(自己总结的)
10,用来判断某个值是否存在哈希表中:containsKey()
if(result.containsKey(temp)){}
练习题和讲解
有效的字母移位词
使用int
前置知识:
字母a-z,A-Z的ASCII码是连续的。
所以’a’-‘a’=0;‘z’-‘a’=25;
class Solution {
public boolean isAnagram(String s, String t) {
int[] arr=new int[26]; //用来存储26个字母出现的次数
for(int i=0;i<s.length();i++){ //字符串用length()方法,数组为length。因为对于字符串,length是方法,数组是内置属性。
arr[s.charAt(i)-'a']++; //charAt(i)获取字符串中i位置的字符。 我们在对于的下标的位置+1.比如出现z,则是'z'-'a',在25这个位置+1.
};
for(int i=0;i<t.length();i++){
arr[t.charAt(i)-'a']--; //目的同样,在对应位置-1,抵消s字符串中出现的字母。
};
for(int a:arr){ //增强for循环方法。
if(a!=0){ //进行判断,如果不等0,证明两个里面的出现字母的数量不一致。
return false;
}
}
return true;
}
}
349. 两个数组的交集
349. 两个数组的交集
使用set
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可以直接去重
Set<Integer> resSet = new HashSet<>();
//遍历数组1
for (int i : nums1) {
set1.add(i);
}
//遍历数组2的过程中判断哈希表中是否存在该元素
for (int i : nums2) {
if (set1.contains(i)) { //contains() 判断这个值是否在哈希表中
resSet.add(i);
}
}
//另外申请一个数组存放setRes中的元素,最后返回数组
int[] arr = new int[resSet.size()];
int j = 0;
for(int i : resSet){
arr[j++] = i;
}
return arr;
}
}
1. 两数之和
1. 两数之和
使用map(需要存放 key value)
class Solution {
public int[] twoSum(int[] nums, int target) {
// 创建一个 HashMap 来存储数字及其对应的索引
Map<Integer, Integer> map = new HashMap<>();
int n = nums.length;
// 遍历数组
for (int i = 0; i < n; i++) {
// 计算当前元素的补数
int temp = target - nums[i];
// 检查补数是否在 HashMap 中
if (map.containsKey(temp)) {
// 找到结果,那么返回当前索引和补数的索引
return new int[]{map.get(temp), i};
}
// 如果没有找到补数,就把当前数字和它的索引放入 HashMap
map.put(nums[i], i);
}
// 如果没有找到,返回一个空数组,考虑到题目保证有解这里可以省略
return new int[]{};
}
}
454. 四数相加 II
454. 四数相加 II
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
//不仅要保存值,还需要保存其出现次数,所以使用map(key,value)来进行存储数据。
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//统计两个数组中的元素之和,同时统计出现的次数,放入map
for (int i : nums1) {
for (int j : nums2) {
int sum = i + j;
map.put(sum, map.getOrDefault(sum, 0) + 1);//getOrDefault这个的意思是,如果存在,返回存在的值,不存在返回default0
}
}
//统计剩余的两个元素的和,在map中找是否存在相加为0的情况,同时记录次数
for (int i : nums3) {
for (int j : nums4) {
//因为本题不去重,所以有不同组合,需要统计的值为 res+sum(对应的值);
res += map.getOrDefault(0 - i - j, 0);
}
}
return res;
}
}
15. 三数之和
15. 三数之和
使用哈希集合:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// 如果第一个元素大于零,不可能凑成三元组
if (nums[i] > 0) {
return result;
}
// 三元组元素a去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
HashSet<Integer> set = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
// 三元组元素b去重
if (j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) {
continue;
}
int c = -nums[i] - nums[j];
if (set.contains(c)) {
result.add(Arrays.asList(nums[i], nums[j], c));
set.remove(c); // 三元组元素c去重
} else {
set.add(nums[j]);
}
}
}
return result;
}
}
使用双指针(更为推荐)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//二维集合,因为不止一个集合
List<List<Integer>> ans=new ArrayList();
int len=nums.length;
//如果值小于3,则没有意义
if(len<3||nums==null) return ans;
//排序,更方便我们双指针的移动
Arrays.sort(nums);
//定i的位置,然后动left和right两个指针的位置来凑0
for(int i=0;i<len;i++){
//如果第一个i都>0,则不可能三数之和为0
if(nums[i]>0) break;
//题目去重,所以我们判断前一位值如果等于后一位,则跳过。
if(i>0&&nums[i]==nums[i-1]) continue;
//定义左右指针
int L=i+1;
int R=len-1;
while(L<R){
int sum =nums[i]+nums[R]+nums[L];
//如果相等,则添加进入二维数组中
if(sum==0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
//归零
while(L<R&& nums[L]==nums[L+1]) L++;
while(L>R&& nums[R]==nums[R-1]) R--;
L++;
R--;
}
//和小,就左指针右移,和大,就右指针左移
else if(sum<0)L++;
else if(sum>0)R--;
}
}
//返回二维数组。
return ans;
}
}
总结
哈希表理论基础
在关于哈希表,你该了解这些! (opens new window)中,我们介绍了哈希表的基础理论知识,不同于枯燥的讲解,这里介绍了都是对刷题有帮助的理论知识点。
一般来说哈希表都是用来快速判断一个元素是否出现集合里。
对于哈希表,要知道哈希函数和哈希碰撞在哈希表中的作用。
哈希函数是把传入的key映射到符号表的索引上。
哈希碰撞处理有多个key映射到相同索引上时的情景,处理碰撞的普遍方式是拉链法和线性探测法。
接下来是常见的三种哈希结构:
数组
set(集合)
map(映射)
在C++语言中,set 和 map 都分别提供了三种数据结构,每种数据结构的底层实现和用途都有所不同,在关于哈希表,你该了解这些! (opens new window)中我给出了详细分析,这一知识点很重要!
例如什么时候用std::set,什么时候用std::multiset,什么时候用std::unordered_set,都是很有考究的。
只有对这些数据结构的底层实现很熟悉,才能灵活使用,否则很容易写出效率低下的程序。