哈希知识基础
文章链接:https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%93%88%E5%B8%8C%E8%A1%A8
242.有效的字母异位词
题目链接:https://leetcode.cn/problems/valid-anagram/description/
使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。
思路:简易的哈希表
设置一个数组,其实就是一个简单哈希表,大小为26 就可以了,初始化为0,因为字符a到字符z的ASCII也是26个连续的数值。
这个数组用来记录字符串s里字符出现的次数,把字符映射到数组也就是哈希表的索引下标上。
只需要分别的遍历一下两个字符串,遍历第一个字符串的时候,对应的位置+1;遍历第二个字符串的时候,对应的位置-1。
最后检查一下,如果数组里有的元素不为0,说明一定是谁多了字符或者谁少了字符,return false
如果数组里所有的元素都为0,说明找到了,return true
class Solution {
public boolean isAnagram(String s, String t) {
int[] a = new int[26];
if(s.length()!=t.length())
return false;
for(int i=0;i<s.length();i++){
a[s.charAt(i)-'a'] ++;
}
for(int i=0;i<t.length();i++){
a[t.charAt(i)-'a'] --;
}
for(int count:a)
{
if(count!=0)
return false;
}
return true;
}
}
时间复杂度 O(n)
空间复杂度 O(1)
349. 两个数组的交集
题目连接:https://leetcode.cn/problems/intersection-of-two-arrays/description/
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。尝试用一遍扫描实现。
解法:使用HashSet
这道题目,主要要学会使用HashSet求解即可。
但是要注意,使用数组来做哈希的题目,是因为题目都限制了数值的大小。
而这道题目没有限制数值的大小,就无法使用数组来做哈希表了。
而且如果哈希值比较少、特别分散、跨度非常大,使用数组就造成空间的极大浪费。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
for(int val:nums1)
set1.add(val);
for(int val:nums2)
{
if(set1.contains(val))
resSet.add(val);
}
// 方法1:直接转成数组
// return resSet.stream().mapToInt(x->x).toArray();
// 方法2:定义一个数组
int[] arr = new int[resSet.size()];
int j = 0;
for(int val:resSet){
arr[j++] = val;
}
return arr;
}
}
时间复杂度 O(m+n)
空间复杂度 O(m+n) ,其中 m 和 n 分别是两个数组的长度。
202. 快乐数
题目连接:https://leetcode.cn/problems/happy-number/description/
解法:求两个链表交点节点的指针
当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法了。
题目中说了会 无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要。
还有一个难点就是求和的过程,如果对取数值各个位上的单数操作不熟悉的话,做这道题也会比较艰难。
class Solution {
public int getSum(int n){
int ans = 0;
// 不能写n%10,假如是100就直接不执行了
while(n >0){
ans += (n%10)*(n%10);
n = n/10;
}
return ans;
}
public boolean isHappy(int n) {
int result = n;
Set<Integer>set = new HashSet<>();
// 循环
// while(true){
// result = getSum(result);
// System.out.println(result);
// if(result==1)
// return true;
// else if(set.contains(result))
// return false;
// else
// set.add(result);
// }
// 第二种循环写法
while(n!=1 && !set.contains(n)){
set.add(n);
n = getSum(n);
}
return n==1;
}
}
时间复杂度:O(logn)
空间复杂度:O(logn)
1. 两数之和
题目连接:https://leetcode.cn/problems/two-sum/
解法1:快慢指针法
很明显暴力的解法是两层for循环查找,时间复杂度是O(n^2)。
当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到哈希法。
因为本题,我们不仅要知道元素有没有遍历过,还要知道这个元素对应的下标,需要使用 key value结构来存放,key来存元素,value来存下标,那么使用map正合适。
再来看一下使用数组和set来做哈希法的局限。
(1)数组的大小是受限制的,而且如果元素很少,而哈希值太大会造成内存空间的浪费。
(2)set是一个集合,里面放的元素只能是一个key,而两数之和这道题目,不仅要判断y是否存在而且还要记录y的下标位置,因为要返回x 和 y的下标。所以set 也不能用。
map目的用来存放我们访问过的元素,因为遍历数组的时候,需要记录我们之前遍历过哪些元素和对应的下标,这样才能找到与当前元素相匹配的(也就是相加等于target)
map中的存储结构为 {key:数据元素,value:数组元素对应的下标}
在遍历数组的时候,只需要向map去查询是否有和目前遍历元素匹配的数值,如果有,就找到的匹配对,如果没有,就把目前遍历的元素放进map中,因为map存放的就是我们访问过的元素。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
Map<Integer,Integer>map = new HashMap<>();
for(int i=0;i<nums.length;i++){
int tmp = target-nums[i];
if(map.containsKey(tmp))
{
res[0] = map.get(tmp);
res[1] = i;
return res;
}else{
map.put(nums[i],i);
}
}
return res;
}
}
时间复杂度:O(n)
空间复杂度:O(n)