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 {};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21