【LeetCode 熱題 100】（一）哈希

1. 兩數之和

class Solution {public int[] twoSum(int[] nums, int target) {int length = nums.length;// 1.聲明一個hashmap {nums[i], i}HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < length; i++) {int second = target - nums[i];if(map.containsKey(second)){int j = map.get(second);return new int[]{i,j};}map.put(nums[i],i);}return new int[]{};     }
}

這段代碼實現了在整數數組 nums 中找到兩個數，使它們的和等于給定的目標值 target，并返回這兩個數的索引。其解題思路基于 哈希表優化查找效率，具體步驟如下：

解題思路描述：

初始化哈希表：
- 創建一個 HashMap<Integer, Integer>，鍵（Key）存儲數組元素的值，值（Value）存儲該元素的索引。
- 目標：通過值快速查找對應的索引。
遍歷數組：
- 對每個元素 nums[i]，計算其配對值 second = target - nums[i]（即滿足 nums[i] + second = target 的值）。
檢查配對值是否存在：
- 在哈希表中查找 second：
  - 若存在：說明 second 是之前遍歷過的某個元素的值，其索引 j = map.get(second) 與當前索引 i 即為解。
  - 直接返回 {i, j}（順序為 i 在后，j 在前）。
- 若不存在：將當前值 nums[i] 及其索引 i 存入哈希表，繼續遍歷。
遍歷結束處理：
- 若循環結束未找到解，返回空數組 {}（題目保證有解，此步為語法完整性）。

關鍵點分析：

高效查找：哈希表在平均 O(1) 時間內完成 containsKey 和 get 操作，將整體時間復雜度優化至 O(n)。
避免重復使用：先檢查配對值再存入當前值，確保不會將同一元素使用兩次（例如 target = 4, nums[i] = 2 時，先檢查 2 是否已存在，再存入當前 2）。
順序無關：返回索引順序取決于遍歷順序（j 為哈希表中存儲的較早索引，i 為當前索引）。

示例說明：

輸入：nums = [3, 2, 4], target = 6
步驟：
1. i=0：nums[0]=3 → second=3（6-3），哈希表為空 → 存入 (3,0)。
2. i=1：nums[1]=2 → second=4（6-2），哈希表無 4 → 存入 (2,1)。
3. i=2：nums[2]=4 → second=2（6-4），哈希表存在 2（索引 j=1）→ 返回 {2, 1}。

復雜度：

時間復雜度：O(n)，遍歷數組一次。
空間復雜度：O(n)，哈希表存儲最多 n 個元素。

此方法以空間換時間，高效解決了“兩數之和”問題。

49. 字母異位詞分組

class Solution {public List<List<String>> groupAnagrams(String[] strs) {HashMap<String, List<String>> map = new HashMap<>();for (String item : strs) {// 1. 聲明字母數組int[] count1 = new int[26];// 2. 將字母轉換位對應的ascii 存儲到數組下標for (int i = 0; i < item.length(); i++) {char c = item.charAt(i);int poi = c - 'a';count1[poi] = count1[poi] + 1;}// 3. 在將數組下標轉換位字母StringBuilder sb = new StringBuilder();for (int i = 0; i < 26; i++) {if(count1[i] != 0){sb.append((char) (i + 'a'));sb.append(count1[i]);}}// 4. 判斷map中鍵中是否包含String key = sb.toString();List<String> list1 = map.getOrDefault(key, new LinkedList<>());list1.add(item);map.put(key, list1);}List<List<String>> list = new LinkedList<>(map.values());return list;}
}

解題思路描述

這段代碼實現了將一組字符串按字母異位詞（Anagram） 分組的功能。字母異位詞指字母相同但排列不同的字符串（如 “eat” 和 “tea”）。核心思路是 為每個字符串生成唯一的特征編碼作為哈希表的鍵，具體步驟如下：

1. 初始化哈希表

HashMap<String, List<String>> map = new HashMap<>();

鍵（Key）：字符串的特征編碼（字母出現頻次的唯一標識）
值（Value）：所有具有相同特征編碼的字符串組成的列表

2. 遍歷所有字符串

對每個字符串 item 執行以下操作：

for (String item : strs) {// 步驟2.1 ~ 2.4
}

2.1 統計字母頻次

int[] count1 = new int[26];
for (int i = 0; i < item.length(); i++) {char c = item.charAt(i);int poi = c - 'a';  // 將字母映射到 0-25 的索引count1[poi]++;      // 對應字母計數+1
}

創建長度 26 的數組（對應 a-z）
遍歷字符串中的每個字符，在數組中記錄其出現次數

2.2 生成特征編碼（關鍵步驟）

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {if(count1[i] != 0){sb.append((char) (i + 'a')); // 添加字母sb.append(count1[i]);        // 添加出現次數}
}
String key = sb.toString();

將統計數組轉換為唯一字符串標識（如 “a2b1” 表示 a 出現 2 次，b 出現 1 次）
為什么有效：
字母異位詞的統計結果相同 → 生成的 key 相同
非字母異位詞統計結果不同 → 生成的 key 不同

2.3 分組存儲到哈希表

List<String> list1 = map.getOrDefault(key, new LinkedList<>());
list1.add(item);
map.put(key, list1);

若 key 不存在：創建新列表
若 key 已存在：獲取現有列表
將當前字符串添加到對應列表

3. 返回分組結果

return new LinkedList<>(map.values());

哈希表的 values() 就是所有分組結果
直接轉換為列表返回（每個子列表是一組字母異位詞）

關鍵優勢

精確分組
通過字母頻次統計確保只有字母異位詞共享同一 key
避免排序
相比對每個字符串排序（O(klogk)），統計頻次只需 O(k)（k 為字符串長度）
哈希表高效操作
插入和查詢操作均攤時間復雜度 O(1)

復雜度分析

時間復雜度：O(n × k)
- n：字符串數組長度
- k：最長字符串長度（每個字符串需遍歷統計）
空間復雜度：O(n × k)
- 哈希表存儲所有字符串的特征編碼和分組列表

示例說明

輸入：["eat", "tea", "tan"]
處理過程：

“eat” → 統計：a1,e1,t1 → 特征碼：“a1e1t1”
“tea” → 統計：a1,e1,t1 → 特征碼：“a1e1t1” → 與 “eat” 同組
“tan” → 統計：a1,n1,t1 → 特征碼：“a1n1t1” → 新分組
輸出：[ ["eat","tea"], ["tan"] ]

128. 最長連續序列

class Solution {public int longestConsecutive(int[] nums) {int max_long = 0;Set<Integer> hashSet = new HashSet<>();for (int num : nums) {hashSet.add(num);}for (int num : hashSet) {// 1.判斷當前的前一位是否在集合中if(!hashSet.contains(num - 1)){int curr_num = num;int current_long = 1;// 2.全局最大的子序列和當前子序列長度while (hashSet.contains(curr_num + 1)){curr_num = curr_num + 1;current_long = current_long + 1;}max_long = Math.max(current_long, max_long);}}return max_long;}
}

解題思路描述

這段代碼實現了在未排序整數數組中尋找最長連續序列長度的功能。核心思路是 利用哈希集合實現高效查找，并通過 跳過非連續序列起點 避免重復計算，具體步驟如下：

1. 初始化哈希集合

Set<Integer> hashSet = new HashSet<>();
for (int num : nums) {hashSet.add(num);
}

將所有數字存入哈希集合，實現 O(1) 時間復雜度的查找
自動去除重復元素，避免冗余處理

2. 尋找連續序列起點

for (int num : hashSet) {if(!hashSet.contains(num - 1)) { // 關鍵判斷// 處理連續序列...}
}

核心思想：只從連續序列的起點開始計算
判斷條件：num-1 不存在于集合中 → 說明 num 是某個連續序列的最小值（起點）
為什么有效：
若非起點（如 num=3 時 num-1=2 存在），說明它屬于某個更長序列的中間部分，后續會被起點覆蓋計算

3. 擴展連續序列

int curr_num = num;
int current_long = 1;
while (hashSet.contains(curr_num + 1)) {curr_num++;          // 移動到下一個數字current_long++;      // 序列長度+1
}

從起點 num 開始向后擴展序列（num, num+1, num+2,...）
每找到一個連續后繼數字：
- 移動當前數字指針 curr_num
- 增加當前序列長度 current_long
當 curr_num+1 不存在時，序列終止

4. 更新全局最大值

max_long = Math.max(current_long, max_long);

比較當前序列長度與歷史最大值
始終保持 max_long 為遍歷過程中的最大序列長度

5. 返回結果

return max_long;

返回全局最長連續序列長度

關鍵優勢

高效去重
使用 HashSet 自動處理重復元素，避免無效計算
起點優化策略
僅從序列起點開始擴展，確保每個連續序列只計算一次
時間復雜度優化
看似嵌套循環，實際每個元素最多被訪問兩次（集合構建+序列擴展），整體 O(n) 復雜度

復雜度分析

時間復雜度：O(n)
- 集合構建：O(n)
- 序列擴展：每個元素最多被內層循環訪問一次
空間復雜度：O(n)
- 哈希集合存儲所有元素

示例說明

輸入：[100, 4, 200, 1, 3, 2]
處理過程：

構建集合：{1, 2, 3, 4, 100, 200}
遍歷元素：
- 100：99不存在 → 起點 → 向后擴展：101不存在 → 長度=1
- 4：3存在 → 非起點 → 跳過
- 200：199不存在 → 起點 → 向后擴展：201不存在 → 長度=1
- 1：0不存在 → 起點 → 向后擴展：2,3,4存在 → 5不存在 → 長度=4
- 2和3：非起點 → 跳過
返回最大值：4（序列 1→2→3→4）