LeetCode热题100——哈希表

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。可以按任意顺序返回答案。

// 题解思路：使用哈希表查找遍历目标（无序）
vector<int> twoSum(vector<int>& nums, int target) {if (nums.empty()) {return {};}std::unordered_map<int, int> map;for (int i = 0; i < nums.size(); ++i) {if (map.count(target - nums[i])) {return {i, map[target - nums[i]]};} else {map[nums[i]] = i;}}return {};
}

2.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

// 题解思路：排序后分组
vector<vector<string>> groupAnagrams(vector<string>& strs) {std::unordered_map<string, vector<string>> map;for (const auto& str : strs) {string key = str;sort(key.begin(), key.end());map[key].emplace_back(str);}vector<vector<string>> result;for (auto iter = map.begin(); iter != map.end(); ++iter) {result.emplace_back(iter->second);}return result;
}

3.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

// 题解思路：排序去重，相邻计算统计最大长度
int longestConsecutive(vector<int>& nums) {if (nums.empty()) {return 0;}sort(nums.begin(), nums.end());auto iter = std::unique(nums.begin(), nums.end());nums.erase(iter, nums.end());int update_count = 1;int max_length = 1;for (int i = 0; i < nums.size() - 1; ++i) {if (nums[i+1] - nums[i] == 1) {max_length = std::max(max_length, ++update_count);} else {update_count = 1;max_length = std::max(max_length, update_count);}}return max_length;
}