哈希表法四部曲
哈希表
給定表 M，存在函數 f(key)，對任意給定的關鍵字值 key，代入函數後若能得到包含該關鍵字的記錄在表中的地址，則稱表 M 爲哈希 (Hash）表，函數 f(key) 爲哈希(Hash) 函數。
關鍵碼值與地址一一映射
適用場景
適用於關鍵字與某一值一一對應，即 可使用鍵值對 map，而 hashmap 是鍵值對中較好的實現類
關鍵詞：一一對應
遍歷哈希表的四種方式
1public static void main(String[] args) {
2 Map<String,String> map=new HashMap<String,String>();
3 map.put("1", "value1");
4 map.put("2", "value2");
5 map.put("3", "value3");
6 map.put("4", "value4");
7
8 //第一種：普通使用，二次取值
9 // 遍歷鍵，取出值
10 System.out.println("\n通過Map.keySet遍歷key和value：");
11 for(String key:map.keySet()) {
12 System.out.println("Key: "+key+" Value: "+map.get(key));
13 }
14
15 //第二種
16 // 使用Map.entrySet()的迭代器
17 System.out.println("\n通過Map.entrySet使用iterator遍歷key和value: ");
18 Iterator map1it=map.entrySet().iterator();
19 while(map1it.hasNext()) {
20 Map.Entry<String, String> entry=(Entry<String, String>) map1it.next();
21 System.out.println("Key: "+entry.getKey()+" Value: "+entry.getValue());
22 }
23
24 //第三種：推薦，尤其是容量大時
25 // foreach
26 System.out.println("\n通過Map.entrySet遍歷key和value");
27 for(Map.Entry<String, String> entry: map.entrySet()) {
28 System.out.println("Key: "+ entry.getKey()+ " Value: "+entry.getValue());
29 }
30
31 //第四種
32 // 遍歷value
33 System.out.println("\n通過Map.values()遍歷所有的value，但不能遍歷key");
34 for(String v:map.values()) {
35 System.out.println("The value is "+v);
36 }
37 }
38
39
輸出結果：
1通過Map.keySet遍歷key和value：
2Key: 1 Value: value1
3Key: 2 Value: value2
4Key: 3 Value: value3
5Key: 4 Value: value4
6
7通過Map.entrySet使用iterator遍歷key和value:
8Key: 1 Value: value1
9Key: 2 Value: value2
10Key: 3 Value: value3
11Key: 4 Value: value4
12
13通過Map.entrySet遍歷key和value
14Key: 1 Value: value1
15Key: 2 Value: value2
16Key: 3 Value: value3
17Key: 4 Value: value4
18
19通過Map.values()遍歷所有的value，但不能遍歷key
20The value is value1
21The value is value2
22The value is value3
23The value is value4
24
25
【推薦】使用 entrySet 遍歷 Map 類集合 KV，而不是 keySet 方式進行遍歷。
說明：keySet 其實是遍歷了 2 次，一次是轉爲 Iterator 對象，另一次是從 hashMap 中取出 key 所對應的 value。而 entrySet 只是遍歷了一次就把 key 和 value 都放到了 entry 中，效 率更高。如果是 JDK8，使用 Map.foreach 方法。
正例：values() 返回的是 V 值集合，是一個 list 集合對象; keySet() 返回的是 K 值集合，是一個 Set 集合對象; entrySet() 返回的是 K-V 值組合集合。
記錄數組中元素出現頻數
遍歷 nums1，使用哈希表存儲關鍵字，以及他們出現的次數
方法一：遇到空的就賦初值，非空就 + 1
1// 1. 遍歷nums1，使用哈希表存儲關鍵字，以及他們出現的次數
2Map<Integer, Integer> map = new HashMap<>();
3
4for (int i = 0; i < nums1.length; i++) {
5 if (map.get(nums1[i]) != null) {
6 map.put(nums1[i], map.get(nums1[i])+1);
7 } else {
8 map.put(nums1[i], 1);
9 }
10}
11
12
方法二：使用getOrDefault()
1Map<Integer, Integer> map = new HashMap<Integer, Integer>();
2
3for (int num : nums1) {
4 int count = map.getOrDefault(num, 0) + 1;
5 map.put(num, count);
6}
7
8
方法三：如果元素固定，那麼我們可以就使用一個一維數組來存儲他們出現的頻數。這也是哈希表法。遍歷字符串 p，記錄字符頻數
1int[] sArr = new int[26];
2
3for (int i = 0; i < p.length(); i++) {
4 sArr[s.charAt(i) - 'a']++;
5}
6
7
方法四：如果要求元素只出現一次 或者判斷是否有重複元素，那就可以用哈希集合
1Set<Integer, Integer> set = new HashSet<Integer>();
2
3for (int num : nums1) {
4 // 添加此元素至 Set，加入失敗那就代表有重複
5 if(!set.add(num)) {
6 return false;
7 }
8}
9
10
實例
- 兩數之和
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和爲目標值 的那 兩個 整數，並返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。
你可以按任意順序返回答案。
示例 1：輸入：nums = [2,7,11,15], target = 9 輸出：[0,1] 解釋：因爲 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：輸入：nums = [3,2,4], target = 6 輸出：[1,2]
示例 3：輸入：nums = [3,3], target = 6 輸出：[0,1]
答案
1class Solution {
2 public int[] twoSum(int[] nums, int target) {
3
4 // 哈希表用來存放（關鍵字，下標）
5 Map<Integer, Integer> map = new HashMap<>();
6
7 // 遍歷數組，每次遇到一個元素判斷哈希表裏面有沒有與其對應的target - nums[i]元素
8 // 如果有就返回下標，如果沒有就把它的關鍵字和下標放進去，
9 for (int i = 0; i < nums.length; i++) {
10
11 Integer index = map.get(target - nums[i]);
12 if (index != null) {
13 return new int[]{index, i};
14 } else {
15 map.put(nums[i], i);
16 }
17 }
18 return null;
19 }
20}
21
22
- 有效的字母異位詞
給定兩個字符串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。
示例 1:
輸入: s = "anagram", t = "nagaram" 輸出: true 示例 2:
輸入: s = "rat", t = "car" 輸出: false 說明: 你可以假設字符串只包含小寫字母。
進階: 如果輸入字符串包含 unicode 字符怎麼辦？你能否調整你的解法來應對這種情況？
- 答案
方法一：排序
t 是 s 的異位詞等價於「兩個字符串排序後相等」。因此我們可以對字符串 s 和 t 分別排序，看排序後的字符串是否相等即可判斷。此外，如果 s 和 t 的長度不同，t 必然不是 s 的異位詞。
1class Solution {
2 public boolean isAnagram(String s, String t) {
3 if (s.length() != t.length()) {
4 return false;
5 }
6 char[] str1 = s.toCharArray();
7 char[] str2 = t.toCharArray();
8 Arrays.sort(str1);
9 Arrays.sort(str2);
10 return Arrays.equals(str1, str2);
11 }
12}
13
14
複雜度分析
這依賴於語言的細節；
這取決於函數的設計方式，例如，可以將函數參數類型更改爲 char[]。
方法二：哈希表
前面我們說過了關鍵碼值與地址一一映射，就可以稱爲哈希表（即 散列表），所以此處的方法也可以稱爲哈希表法。
從另一個角度考慮，t 是 s 的異位詞等價於「兩個字符串中字符出現的種類和次數均相等」。由於字符串只包含 26 個小寫字母，因此我們可以維護一個長度爲 26 的頻次數組 table，先遍歷記錄字符串 s 中字符出現的頻次，然後遍歷字符串 t，減去 table 中對應的頻次，如果出現 table[i]<0，則說明 t 包含一個不在 s 中的額外字符，返回 false 即可。
1class Solution {
2 public boolean isAnagram(String s, String t) {
3 if (s.length() != t.length()) {
4 return false;
5 }
6 int[] table = new int[26];
7 for (int i = 0; i < s.length(); i++) {
8 table[s.charAt(i) - 'a']++;
9 }
10 for (int i = 0; i < t.length(); i++) {
11 table[t.charAt(i) - 'a']--;
12 if (table[t.charAt(i) - 'a'] < 0) {
13 return false;
14 }
15 }
16 return true;
17 }
18}
19
20
對於進階問題，Unicode 是爲了解決傳統字符編碼的侷限性而產生的方案，它爲每個語言中的字符規定了一個唯一的二進制編碼。而 Unicode 中可能存在一個字符對應多個字節的問題，爲了讓計算機知道多少字節表示一個字符，面向傳輸的編碼方式的 UTF−8 和 UTF−16 也隨之誕生逐漸廣泛使用，具體相關的知識讀者可以繼續查閱相關資料拓展視野，這裏不再展開。
回到本題，進階問題的核心點在於「字符是離散未知的」，因此我們用哈希表維護對應字符的頻次即可。同時讀者需要注意 Unicode 一個字符可能對應多個字節的問題，不同語言對於字符串讀取處理的方式是不同的。
1class Solution {
2 public boolean isAnagram(String s, String t) {
3 if (s.length() != t.length()) {
4 return false;
5 }
6 Map<Character, Integer> table = new HashMap<Character, Integer>();
7 for (int i = 0; i < s.length(); i++) {
8 char ch = s.charAt(i);
9 table.put(ch, table.getOrDefault(ch, 0) + 1);
10 }
11 for (int i = 0; i < t.length(); i++) {
12 char ch = t.charAt(i);
13 table.put(ch, table.getOrDefault(ch, 0) - 1);
14 if (table.get(ch) < 0) {
15 return false;
16 }
17 }
18 return true;
19 }
20}
21
22
複雜度分析
-
時間複雜度：O(n)，其中 n 爲 s 的長度。
-
空間複雜度：O(S)，其中 S 爲字符集大小，此處 S=26。
劍指 Offer 61. 撲克牌中的順子
從撲克牌中隨機抽 5 張牌，判斷是不是一個順子，即這 5 張牌是不是連續的。2～10 爲數字本身，A 爲 1，J 爲 11，Q 爲 12，K 爲 13，而大、小王爲 0 ，可以看成任意數字。A 不能視爲 14。
示例 1:
1輸入: [1,2,3,4,5]
2輸出: True
3
4
示例 2:
1輸入: [0,0,1,2,5]
2輸出: True
3
4
答案
1class Solution {
2 public boolean isStraight(int[] nums) {
3 Set<Integer> repeat = new HashSet<>();
4 int max = 0, min = 14;
5 for(int num : nums) {
6 if(num == 0) continue; // 跳過大小王
7 max = Math.max(max, num); // 最大牌
8 min = Math.min(min, num); // 最小牌
9 // 添加此牌至 Set，加入失敗那就代表有重複
10 if(!repeat.add(num)) return false; // 若有重複，提前返回 false
11
12 }
13 return max - min + 1 <= 5; // 最大牌 - 最小牌 + 1 <= 5 則可構成順子，因爲包含有0、0、0、9、11的情況
14 }
15}
16
17
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/03y8UJnH8DI6dhsNPpYChw