此篇文章与大家分享分治算法关于哈希表相关算法的专题
如果有不足的或者错误的请您指出!
1.哈希表简介
哈希实际上可以简单认为是一个存储数据的容器,用于快速查找某个元素,时间复杂度仅为O(1),怎么有时候需要频繁查找某一个数的时候,就可以使用哈希表
那我们怎么使用哈希表呢??
分成两种,一种是使用编程语言自带的容器,如java里面的Map和Set
另外一种是我们自定义一个数组来作为哈希表,这种通常出现在我们对字符串中的字符进行操作的时候,我们可以自定义一个int[26] (如果都是小写字符),或者是当数据范围比较小的时候,使用数组模拟哈希表往往是更快的
2.两数之和
题目:两数之和
2.1解析
最容易想到的就是暴力枚举,即两个两个枚举求和,看看和是否满足为target
而暴力枚举也分成两种:
第一种是定住一个数,从这个数往后遍历,看看是否能找到值为target - nums[i]的数
第二种是定住一个数,从这个数往前遍历,看看是否能找到值为target - nums[i]的数
但是时间复杂度都达到的O(n^2)级别
而对于第二种,我们的优化策略是比较好想的,就是利用hash表,当i从前往后遍历的时候,就可,当我们回头找前面的数中是否有值为target - nums[i]的时,直接在哈希表中寻找即可,时间复杂度为O(n)
2.2题解
class Solution { public int[] twoSum(int[] nums, int target) { Map hash = new HashMap<>();
for(int i = 0; i < nums.length; i++){ if(hash.containsKey(target-nums[i])){ return new int[]{hash.get(target-nums[i]),i};
}
hash.put(nums[i],i);
}
return new int[]{-1,-1};
}
}
3.判定是否互为字符重排
题目:判定是否互为字符重排
3.1解析
两个互为重排字符串的字符串,首先字符串的长度一定想等,其次,其中每个字符的出现的次数也一定相等.那么我们直接用哈希表来统计其中一串字符串中每个字符出现的次数,接着遍历另一串字符串,每次将前面的哈希表中对应字符的个数减1,如果出现某一个字符出现的个数为负数,那么就一定不是重排字符串
而我们这里最优的解法就是用数组模拟哈希表
3.2题解
class Solution { public boolean CheckPermutation(String s1, String s2) { if(s1.length() != s2.length()){ return false;
}
int[] hash = new int[26];
for(char ch : s1.toCharArray()){ hash[ch-'a']++;
}
for(char ch : s2.toCharArray()){ hash[ch-'a']--;
if(hash[ch-'a'] == -1){ return false;
}
}
return true;
}
}
4.存在重复元素
题目:存在重复元素
4.1解析
与第二题相似,只不过这道题只需要存储值即可,所以直接用set
4.2题解
class Solution { public boolean containsDuplicate(int[] nums) { Set hash = new HashSet<>();
for(int x : nums){ if(hash.contains(x)){ return true;
}
hash.add(x);
}
return false;
}
}
5.存在重复元素II
题目:存在重复元素II
5.1解析
和上一道题思路一样,只不过多了个判断
有一个细节问题:
当遍历第二个1的时候,第一个1已经在哈希表中存在,但是他们的下标之差不满足 <= k,而此时我们应该让这个1取代前面的1,因为后面如果再遇到1,满足条件也只可能与当前的1
5.2题解
class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Map hash = new HashMap<>();
for(int i = 0; i < nums.length; i++){ if(hash.containsKey(nums[i])){ if(i - hash.get(nums[i]) <= k){ return true;
}
}
hash.put(nums[i],i);
}
return false;
}
}
6.字母异位词分组
题目:字符异位词分组
6.1解析
此题我们就能很好的感受到哈希表的优势了
题目要我们把所有的异位词都组合在一块,那么我们首先就要判断哪些字符串是异位词.我们采用对字符串进行排序的方法,排完序后对字符串进行比较即可
我们可以建立一个HashMap,键是String,存放的是排序后的字符串,值是List< String>
,如果判断某个字符串和此时哈希表中的某个键是异位词,那么直接将这个字符串插到当前的List后面即可
6.2题解
class Solution { public List> groupAnagrams(String[] strs) { Map> hash = new HashMap<>();
for(String str : strs){ char[] tmp = str.toCharArray();
Arrays.sort(tmp);
String key = Arrays.toString(tmp);
if(!hash.containsKey(key)){ hash.put(key,new ArrayList());
}
hash.get(key).add(str);
}
return new ArrayList(hash.values());
}
}