LeetCode热题100：哈希

摘要

题目	知识点
1. 两数之和 - 力扣（LeetCode）	哈希优化查找
49. 字母异位词分组 - 力扣（LeetCode）	哈希表
128. 最长连续序列 - 力扣（LeetCode）	哈希优化查找
560. 和为 K 的子数组 - 力扣（LeetCode）	哈希，前缀和

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

class Solution {
public:
	unordered_map<int, int> mp;
	vector<int> twoSum(vector<int>& nums, int target) {
		for(int i = 0 ; i < nums.size() ; i ++){
			mp[nums[i]] = i;
		}
		for(int i = 0 ; i < nums.size() ; i ++){
			if(mp.count(target-nums[i]) && mp[target-nums[i]] != i){
				return {i, mp[target-nums[i]]};
			}
		}
		return {};
	}
};

字母异位词分组

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

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

class Solution {
public:
	vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 以字母排序后的结果为key，用map对字母异位词进行分组。
		unordered_map<string, int> mp;
		vector<vector<string > > ans;
		for(auto it : strs){
			string s = it;
			sort(s.begin(), s.end());
			if(mp.count(s)){
				ans[mp[s]].push_back(it);
			}else{
				mp[s] = ans.size();
				ans.push_back({it});
			}
		}
		return ans;
	}
};

最长连续序列

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

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

1）排序 + 去重

class Solution {
public:
	int longestConsecutive(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		nums.erase(unique(nums.begin(), nums.end()), nums.end());
		if(nums.empty()) return 0;
		int ans = 1;
		int cnt = 1;
        // 排序后已经是上升数组了
        // 检查每个连续区间有多长即可
		for(int i = 1 ; i < nums.size() ; i ++){
			if(nums[i] == nums[i-1] + 1){
				cnt++;
				ans = max(ans, cnt);
			}else{
				cnt = 1;
			}
		}
		return ans;
	}
};

2）哈希

class Solution {
public:
	int longestConsecutive(vector<int>& nums) {
        //st去重
        unordered_set<int> st;
		for(const auto & it : nums){
			st.insert(it);
		}
        int ans = 0;
        // 若st-1存在，说明是起点，检查该上升序列有多长；
        // 若st-1不存，说明不是起点，下一个。
		for(const auto & it : st){
			if(!st.count(it-1)){
				int x = it;
				int cnt = 1;
				while(st.count(x+1)){
					cnt += 1;
					x += 1;
				}
				ans = max(cnt, ans);
			}
		}
		return ans;
	}
};

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

前缀和，哈希：O(N*logN)

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
	int subarraySum(vector<int>& nums, int k) {
		int ans = 0;
		int pre = 0;
		unordered_map<int, int> mp;
		// 用哈希表记录某个前缀和数值出现了多少次
		// 每次查询pre-k是否存在即可
		for(int i = 0 ; i < nums.size() ; i ++){
			pre += nums[i];
			if(pre == k) ans++;
			if(mp.count(pre-k)){
				ans += mp[pre-k];
			}
			mp[pre] = mp[pre] + 1;
		}
		return ans;
	}
};