当前位置：首页 > article >正文

力扣hot100--＞hash表/map

article 2024/11/4 19:05:03

hash表/map

1. 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 <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 创建一个哈希表（unordered_map），用于存储数组元素及其索引
unordered_map<int, int> unmap;

// 遍历数组中的每个元素
for(int i = 0; i < nums.size(); ++i){
// 查找是否存在一个元素，使得当前元素与之的和等于目标值
auto ite = unmap.find(target - nums[i]);
if(ite != unmap.end()){
// 如果找到这样的元素，返回当前索引和找到的索引
return {i, unmap[target - nums[i]]};
}
// 将当前元素及其索引插入到哈希表中
unmap.insert(pair<int, int>(nums[i], i));
}
// 如果没有找到符合条件的元素，返回空数组
return {};
}
};

解释：

unmap.find(target - nums[i]) 的返回类型是 unordered_map<int, int>::iterator。这个迭代器指向哈希表中与 target - nums[i] 相等的键值对，或者如果没有找到这样的键，则指向 unmap.end()。

使用 auto 可以让代码更简洁和易读。

2. 49. 字母异位词分组

中等

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

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

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

class Solution {
public:
// 函数定义：输入字符串数组，返回分组的异位词
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ss; // 用于存储最终结果的二维向量
unordered_map<string, vector<string>> m; // 哈希表，键为排序后的字符串，值为异位词的向量

// 遍历输入的字符串数组
for(string &s : strs){
string t = s; // 复制当前字符串
sort(t.begin(), t.end()); // 对字符串进行排序，以便找到异位词

// 将原始字符串加入到对应排序后的键的向量中
m[t].push_back(s);
}

// 遍历哈希表，将每个值向量添加到结果中
for(auto it = m.begin(); it != m.end(); ++it){
ss.push_back(it->second); // 将当前异位词组添加到结果向量中
}

return ss; // 返回分组后的异位词
}
};

解释：

sort(s.begin(), s.end()); 这意味着所有异位词（如 "tea" 和 "ate"）在排序后都会转换为相同的字符串（"aet"）。

3. 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 <= 105
-109 <= nums[i] <= 109

class Solution { public: int longestConsecutive(vector<int>& nums) { sort(nums.begin(), nums.end(), less<>()); // 对数组进行排序 int leng = 1; // 当前连续序列的长度 int answer = nums.size() > 0 ? 1 : 0; // 如果数组不为空，初始化为 1；否则为 0

for (int i = 1; i < nums.size(); i++) { // 跳过重复的元素 while (i < nums.size() && nums[i] == nums[i - 1]) { i++; }

// 检查当前元素是否与前一个元素连续 if (i < nums.size() && nums[i] == nums[i - 1] + 1) { leng++; // 增加当前连续序列的长度 answer = max(answer, leng); // 更新最长连续序列的长度 } else { leng = 1; // 重置当前连续序列的长度 } } return answer; // 返回最长连续序列的长度 } };