哈希表理论基础
解决的核心问题：快速判断一个元素是否出现在集合里面
时间复杂度为O（1）
哈希函数: 将值附到哈希表中所用的函数，不可避免出现同时映射到同一个索引下标上
哈希碰撞：如果出现不同值映射到同一个索引下标上面，有两种方法处理
- 拉链法：把不同的值做成链表，就可以索引了
- 线性探测：可以把映射到相同下标的值，分配给空的下标的位置，此方法需保证tableSize > dataSize
常见哈希表实现：数组，set，map
当解决哈希问题时，优先使用unordered_set
牺牲空间来换取时间
242 有效的字母异位词
https://leetcode.com/problems/valid-anagram/description/
数组做哈希表的经典题目
记录元素出现次数时，可以用26长度的数组
记录index 为 charAt(i) - ‘a’ 的次数
然后检查是否都出现过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution{
public boolean isAnagram(String s, String t){
int[] record = new int[26];
for (int i = 0; i < s.length(); i++){
record[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++){
record[t.charAt(i) - 'a']--;
}
for (int i = 0; i < record.length; i++){
if(record[i] != 0){
return false;
}
}
return true;
}
}
|
349 两个数组的交集
https://leetcode.com/problems/intersection-of-two-arrays/description/
输出结果中每个元素唯一，所以包含去重操作，去重就需要想到set的哈希表
在java中需要使用HashSet
- set实现 (推荐)
将数组一遍历一遍之后存到set1里面，这里去重了
再将数组一和数组二比较，出现的存到set2里面
打印成数组
这里可以背下来用法 set.stream().maptoInt(x -> x).toArray();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| import java.util.*;
class Solution{
public int[] intersection(int[] nums1, int[] nums2){
if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0){
return new int[0];
}
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for (int i : nums1){
set1.add(i);
}
for (int i : nums2){
if (set1.contains(i)){
set2.add(i);
}
}
return set2.stream().mapToInt(x -> x).toArray();
int[] result = new int[set2.size()];
int j = 0;
for (int i : set2){
result[j++] = i;
}
return result;
}
}
|
- ArrayList 实现
因为题目规定了nums的长度，和nums所存值的大小，所以可以用数组来做
与242 有效的字母异位词 类似，通过创建数组统计次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| import java.util.*;
class Solution{
public int[] intersection(int[] nums1, int[] nums2){
int[] hash1 = new int[1001];
int[] hash2 = new int[1001];
for (int i : nums1){hash1[i]++;}
for (int i : nums2){hash2[i]++;}
List<Integer> resList = new ArrayList<>();
for (int i = 0; i < hash1.length; i++){
if (hash1[i] != 0 && hash2[i] != 0){
resList.add(i);
}
}
int[] result = new int[resList.size()];
int j = 0;
for (int i : resList){
result[j++] = i;
}
return result;
}
}
|
202 快乐数
https://leetcode.com/problems/happy-number/description/
定义快乐数
每一位的平方和一直计算下去，如果有一次结果为1，则为快乐数
可以判断sum是否重复出现，如果重复出现，则为false，有1则为true
getNextSquareSum 写成方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution{
public boolean isHappy(int n){
Set<Integer> sums = new HashSet<>();
while (n != 1 && !sums.contains(n)){
sums.add(n);
n = getNextSquareSum(n);
}
return n == 1;
}
public int getNextSquareSum(int n){
int sum = 0;
while (n > 0){
int temp = n % 10;
sum += temp * temp;
n /= 10;
}
return sum;
}
}
|
1 两数之和
利用map来做，assign key 和 value的pair
把index作为value， 把数组对应的value变成key
查找差值，return两元素数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import java.util.*;
class Solution{
public int[] twoSum(int[] nums, int target){
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();
if (nums == null || nums.length == 1){
return result;
}
for (int i = 0; i < nums.length; i++){
int temp = target - nums[i];
if (map.containsKey(temp)){
result[1] = i;
result[0] = map.get(temp);
}
map.put(nums[i], i);
}
return result;
}
}
|