哈希表理論基礎(chǔ)
文章講解：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
知識點：
哈希表的內(nèi)部實現(xiàn)原理，哈希函數(shù)，哈希碰撞，以及常見哈希表的區(qū)別，數(shù)組，set 和map。
當(dāng)我們遇到了要快速判斷一個元素是否出現(xiàn)集合里的時候，就要考慮哈希法。
要枚舉的話時間復(fù)雜度是O(n)，但如果使用哈希表的話， 只需要O(1)就可以做到。 ?為什么
假設(shè)有一個包含 1000 個元素的 HashSet：
查找特定元素時，只需要計算哈希值并訪問相應(yīng)的桶，時間復(fù)雜度為 O(1)。
遍歷所有元素時，需要訪問 1000 次，每個元素都要訪問一遍，時間復(fù)雜度為 O(n)。
242.有效的字母異位詞
解題思路：
- anagram：字母構(gòu)成相同，順序不同；完全相同的字符串也是valid anagram
- 刷題時想到hash問題基本就想到三種數(shù)據(jù)結(jié)構(gòu)：數(shù)組，set，map
- 字符串都是由小寫字母組成，它們的ASCII也是26個連續(xù)的數(shù)值，所以可以設(shè)定一個大小為26的數(shù)組hash，a對應(yīng)數(shù)組下標(biāo)為0的位置，以此類推。
- 用hash統(tǒng)計第一個字符串中每一個字母出現(xiàn)的頻率，在遍歷第二個字符串時，每個字母出現(xiàn)的頻率在hash中做減法，如果return 0，就時valid anagram
數(shù)組、set、map使用的場合：
- 數(shù)組：哈希值較小，范圍可控
- set：數(shù)值很大的時候
- map：key對應(yīng)了value
pseudocode
if(s.length != t.length){
return false;
}
int[] hash = new int[26];
for(i=0; i < s.length; i++){
hash[s.charAt[i] - 'a']++;
//計算出當(dāng)前字符在 record 數(shù)組中的索引位置。
//例如，'a' - 'a' = 0, 'b' - 'a' = 1，以此類推。
}
for(i=0; i < t.length; i++){
hash[s.charAt[i] - 'a']--;
}
for(int count : hash){
if(count != 0){
return false;
}
}
return true;
出現(xiàn)的編譯錯誤
數(shù)組或字符串的長度應(yīng)該用.length()方法而不是.length屬性。
s.length(這是數(shù)組的寫法) 應(yīng)改為 s.length()（這是字符串的寫法）
字符串中字符的訪問應(yīng)該使用.charAt(index)方法，而不是.charAt[index]。
s.charAt[i] 應(yīng)改為 s.charAt(i)
對語法還不熟練TT
349. 兩個數(shù)組的交集
建議：本題就開始考慮 什么時候用set 什么時候用數(shù)組，本題其實是使用set的好題，但是后來力扣改了題目描述和 測試用例，添加了 0 <= nums1[i], nums2[i] <= 1000 條件，所以使用數(shù)組也可以了，不過建議大家忽略這個條件。 嘗試去使用set。
注意：返回的交集是去重的。
解題思路：nums1進(jìn)行處理，轉(zhuǎn)變?yōu)楣１淼男问剑鎯ums1中所有的元素；nums2再去遍歷查詢哈希表里是否出現(xiàn)過，如果出現(xiàn)過就放入result集合中。
選擇set來解題：
Java中的set結(jié)構(gòu)
| 集合 | 底層實現(xiàn) | 是否有序 | 數(shù)值是否可以重復(fù) | 能否更改數(shù)值 | 查詢效率 | 增刪效率 |
|---|---|---|---|---|---|---|
| HashSet | 哈希表 | 否 | 否 | 否 | O(1) | O(1) |
| LinkedHashSet | 哈希表 + 鏈表 | 是（插入順序） | 否 | 否 | O(1) | O(1) |
| TreeSet | 紅黑樹 | 是（排序） | 否 | 否 | O(log n) | O(log n) |
pseudocode
//使用HashSet
Set<Integer> resultSet = new HashSet<>(); // 存放結(jié)果，使用Set是為了去重
Set<Integer> numsSet = new HashSet<>();
for (int num : nums1) {
numsSet.add(num);
}
for (int num : nums2) {
if (numsSet.contains(num)) {
resultSet.add(num);
}
}
// 將結(jié)果集轉(zhuǎn)換為數(shù)組
int[] resultArray = new int[resultSet.size()];
int index = 0;
for (int num : resultSet) {
resultArray[index++] = num;
}
return resultArray;
}
或者
return resSet.stream().mapToInt(x -> x).toArray();
- resSet.stream():
stream() 方法將集合轉(zhuǎn)換為一個順序流（Stream<Integer>）。Stream 是一種可以從集合中提取和操作數(shù)據(jù)的高級抽象。 - mapToInt(x -> x):
mapToInt 是一個中間操作，它將流中的每個元素轉(zhuǎn)換為一個 int 值，生成一個 IntStream（整數(shù)流）。 - x -> x 是一個 lambda 表達(dá)式，表示對于流中的每個元素 x，直接將其作為 int 返回。這里的 x 是流中的元素，x -> x 表示不做任何轉(zhuǎn)換。
- toArray():
toArray() 是一個終端操作，它將 IntStream 中的所有元素收集到一個新的 int[] 數(shù)組中。
使用數(shù)組解決：
nt[] hash1 = new int[1002];
int[] hash2 = new int[1002];
for(int i : nums1)
hash1[i]++;
for(int i : nums2)
hash2[i]++;
List<Integer> resList = new ArrayList<>();
for(int i = 0; i < 1002; i++)
if(hash1[i] > 0 && hash2[i] > 0)
resList.add(i);
int index = 0;
int res[] = new int[resList.size()];
for(int i : resList)
res[index++] = i;
return res;
202. 快樂數(shù)
sum重復(fù)出現(xiàn)，就肯定不是快樂數(shù)，為什么呢？
因為只要重復(fù)出現(xiàn)一次就說明會無限循環(huán)，就像之前鏈表那個環(huán)，假設(shè)a1算完等于a2,a2算完等于a3，a3算完等于a1，那么下一次a1算完必定等于a2，再下一次a2算完必定是a3，形成了一個循環(huán)，而這個循環(huán)中不可能有1，因為1平方的結(jié)果永遠(yuǎn)是1,所以肯定有循環(huán)就肯定不是快樂數(shù)，是快樂數(shù)就肯定沒有循環(huán)
class Solution {
public boolean isHappy(int n) {
// 使用HashSet存儲已經(jīng)出現(xiàn)過的數(shù)字，檢測循環(huán)
Set<Integer> record = new HashSet<>();
// 循環(huán)直到n為1或者n已出現(xiàn)過
while(n != 1 && !record.contains(n)){
// 記錄當(dāng)前數(shù)字
record.add(n);
// 計算下一個數(shù)字
n = getNextNum(n);
}
// 如果n為1，則為快樂數(shù)
return n == 1;
}
// getNextNum方法
private int getNextNum(int n){
// res用于存儲每位平方的和
int res = 0;
// 當(dāng)n大于0時繼續(xù)處理
while(n > 0){
// 獲取n的最低位
int temp = n % 10;
// 將最低位的平方加到結(jié)果中
res += temp * temp;
// 移除n的最低位
n = n / 10;
}
// 返回計算后的新數(shù)字
return res;
}
}
1. 兩數(shù)之和
解題思路：
- 想到使用hash法：遇到判斷元素是否在集合中出現(xiàn)過。
- 在遍歷元素B時要判斷之前是否遍歷過和B相加等于target的元素A，如果之前遍歷過，就找到了一對符合的數(shù)值。
- 因為既要知道元素存放的值又要知道存放的數(shù)組下標(biāo)，所以使用Map。
- 為什么要用數(shù)值做key而不是下標(biāo)做key？因為要查找元素是否出現(xiàn)過（Map的作用就是快速查找key）。
Java中的Map：
| 映射 | 底層實現(xiàn) | 是否有序 | 數(shù)值是否可以重復(fù) | 能否更改數(shù)值 | 查詢效率 | 增刪效率 |
|---|---|---|---|---|---|---|
| HashMap | 哈希表 | 否 | 是 | 是 | O(1) | O(1) |
| LinkedHashMap | 哈希表 + 鏈表 | 是（插入順序） | 是 | 是 | O(1) | O(1) |
| TreeMap | 紅黑樹 | 是（排序） | 是 | 是 | O(log n) | O(log n) |
pseudocode
int[] res = new int[2];
if(nums == null || nums.length == 0){
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0;i<nums.length;i++){
//遍歷中尋找查詢的值
int s = target - nums[i];
//如果找到了
if(map.containsKey(s)){
res[1] = i;
res[0] = map.get(s);
break;
}
//如果沒找到，要把當(dāng)前遍歷的元素加入map
map.put(nums[i],i);
}
return res;
自己寫的時候，map.containsKey(s)方法不熟
res[0] = map.get(s); 想了很久拿到下標(biāo)的方法
還要注意if語句中的break
- 這道題目的四個重點：
為什么會想到用哈希表
哈希表為什么用map
本題map是用來存什么的
map中的key和value用來存什么的
