LeetCode 哈希章節

簡單

1. 兩數之和

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 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]
提示：

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只會存在一個有效答案

通過遍歷vector不斷查找如果找到對應的另一個數返回，未找到再插入哈希表，不斷循環。

vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;for (int i = 0; i < nums.size(); ++i) {auto it = hash.find(target - nums[i]);if (it != hash.end())return {i, it->second};hash[nums[i]] = i; // 插入哈希表}return {};
}

202. 快樂數

編寫一個算法來判斷一個數 n 是不是快樂數。

「快樂數」 定義為：

對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
然后重復這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。
如果這個過程 結果為 1，那么這個數就是快樂數。

如果 n 是 快樂數 就返回 true ；不是，則返回 false 。

示例 1：
輸入：n = 19
輸出：true
解釋：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
輸入：n = 2
輸出：false
提示：

1 <= n <= 2^31 - 1

有兩種情況，是快樂數，不斷計算能得到1；不是快樂數，不斷計算會遇到之前出現過的數，會無限循環。與這題141. 環形鏈表類似，可以通過哈希表來記錄出現過的次數即可。

int getHappyNum(int n) {int ret = 0;while (n) {int x = n % 10;ret += x * x;n /= 10;}return ret;
}
bool isHappy(int n) {unordered_map<int, int> hash;while (1) {n = getHappyNum(n);if (n == 1)return true;hash[n]++;if (hash[n] > 1)return false;}return false;
}

217. 存在重復元素

給你一個整數數組 nums 。如果任一值在數組中出現 至少兩次 ，返回 true ；如果數組中每個元素互不相同，返回 false 。

示例 1：

**輸入：**nums = [1,2,3,1]

**輸出：**true

解釋：

元素 1 在下標 0 和 3 出現。

示例 2：

**輸入：**nums = [1,2,3,4]

**輸出：**false

解釋：

所有元素都不同。

示例 3：

**輸入：**nums = [1,1,1,3,3,4,3,2,4,2]

**輸出：**true

提示：

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

bool containsDuplicate(vector<int>& nums) {unordered_set<int> hash;for (int i : nums) {if (hash.find(i) != hash.end())return true;hash.insert(i);}return false;
}

219. 存在重復元素 II

給你一個整數數組 nums 和一個整數 k ，判斷數組中是否存在兩個 不同的索引 i 和 j ，滿足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否則，返回 false 。

示例 1：
輸入：nums = [1,2,3,1], k = 3
輸出：true
示例 2：
輸入：nums = [1,0,1,1], k = 1
輸出：true
示例 3：
輸入：nums = [1,2,3,1,2,3], k = 2
輸出：false
提示：

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

借助貪心思想，哈希表存儲對應最新的下標，可以使abs(i - j)最小。

bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash;for (int i = 0; i < nums.size(); ++i) {if (hash.count(nums[i]))if (i - hash[nums[i]] <= k)return true;hash[nums[i]] = i; // 貪心}return false;
}

面試題 01.02. 判定是否互為字符重排

給定兩個由小寫字母組成的字符串 s1 和 s2，請編寫一個程序，確定其中一個字符串的字符重新排列后，能否變成另一個字符串。

示例 1：
輸入: s1 = "abc", s2 = "bca"
輸出: true 
示例 2：
輸入: s1 = "abc", s2 = "bad"
輸出: false
說明：

0 <= len(s1) <= 100
0 <= len(s2) <= 100

通過哈希表統計字符出現次數是否相等，比排序時間復雜度更低。

bool CheckPermutation(string s1, string s2) {if (s1.size() != s2.size())return false;int hash[128] = {0};for (char ch : s1)++hash[ch];for (char ch : s2) {--hash[ch];if (hash[ch] < 0)return false;}return true;
}

中等

49. 字母異位詞分組

給你一個字符串數組，請你將 字母異位詞 組合在一起。可以按任意順序返回結果列表。

字母異位詞 是由重新排列源單詞的所有字母得到的一個新單詞。

示例 1:
輸入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
輸入: strs = [""]
輸出: [[""]]
示例 3:
輸入: strs = ["a"]
輸出: [["a"]]
提示：

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 僅包含小寫字母

排序哈希

將每個string排序后作為key，建立哈希表。

vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> ans;unordered_map<string, vector<string>> hash;for (auto s : strs) {string tmp = s;sort(tmp.begin(), tmp.end());hash[tmp].push_back(s);}for (auto p : hash)ans.push_back(p.second);return ans;
}

計算哈希

用類似哈希的思想建立數組array<int, 26>對26個字母進行計數，再通過array<int, 26>作為key，建立哈希表。

vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> ans;map<array<int, 26>, vector<string>> hash;array<int, 26> word_hash;for (auto s : strs) {word_hash.fill(0);for (auto& ch : s)word_hash[ch - 'a']++;hash[word_hash].push_back(s);}for (auto p : hash)ans.push_back(p.second);return ans; 
}

128. 最長連續序列

給定一個未排序的整數數組 nums ，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。

請你設計并實現時間復雜度為 O(n) 的算法解決此問題。

示例 1：
輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數字連續序列是 [1, 2, 3, 4]。它的長度為 4。
示例 2：
輸入：nums = [0,3,7,2,5,8,4,6,0,1]
輸出：9
提示：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

通過unoredered_set（構造平均時間復雜度O(n)）去重，以及unoredered_set（查找平均時間復雜度O(1)）來完成對相鄰值的查找比對。判斷是不是連續序列起點降低循環次數，再循環查找相鄰值進行計數。

int longestConsecutive(vector<int>& nums) {int ans = 0;unordered_set<int> num_set;for (auto num : nums)num_set.insert(num);for (auto num : num_set) {// 如果是連續序列的起點if (!num_set.count(num - 1)) {int cur = num;int count = 1;while (num_set.count(num + 1)) {num++;count++;}ans = max(count, ans);}}return ans;
}