(C++哈希表01)
242、有效的字母异位词
用数组模拟哈希表
class Solution {
public:bool isAnagram(string s, string t) {int record[26] = {0};for(int i = 0; i < s.size(); i++) {record[s[i] - 'a']++;}for(int i = 0; i < t.size(); i++) {record[t[i] - 'a']--;}for(int i = 0; i < 26; i++) {if(record[i] != 0) {return false;}}return true;}
};
时间复杂度:O(n + m);
空间复杂度:O(1)
349、两个数组的交集
set占用空间很大,如果题目中的数据有限,优先使用数组。
unordered_set<int> nums_set(nums1.begin(), nums1.end()); 迭代器初始化
find(key)函数,找到key返回begin(),找不到返回end()
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set;//迭代器初始化unordered_set<int> nums_set(nums1.begin(), nums1.end());for(int num: nums2) {//找不到num,find()会返回end()if(nums_set.find(num) != nums_set.end()) {result_set.insert(num);}}return vector<int>(result_set.begin(), result_set.end());}
};
时间复杂度:O(n)
空间复杂度:O(n)
202、快乐数
class Solution {
public:bool isHappy(int n) {unordered_set<int> result_set;int count = 0;result_set.insert(n);while(true) {while(n > 0) {int x = n % 10;count += x * x; n /= 10;}if(count == 1) {return true;}if(result_set.find(count) != result_set.end()) {return false;}result_set.insert(count);n = count;count = 0;}}
};
时间复杂度:O(logn)
空间复杂度:O(logn)
1、两数之和
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> map;for(int i = 0; i < nums.size(); i++) {auto iter = map.find(target - nums[i]);if(iter != map.end()) {return {iter->second, i};}map.insert(pair<int,int>(nums[i], i));}return {};}
};
时间复杂度:O(n)
空间复杂度:O(n)