LeetCode 哈希章节

给定一个整数数组 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 {};
}

编写一个算法来判断一个数 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;
}

给你一个整数数组 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;
}

给你一个整数数组 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;
}

给定两个由小写字母组成的字符串 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;
}

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 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; 
}

给定一个未排序的整数数组 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;
}