242.有效的字母异位词
题目链接 文章讲解 视频讲解
- 时间复杂度 o(n)
- 空间复杂度 o(n)
class Solution {
public:bool isAnagram(string s, string t) {unordered_map<char, int> s_map, t_map;for(char ch : s) s_map[ch]++;for(char ch : t) t_map[ch]++;return s_map == t_map;}
};
349.两个数组的交集
题目链接 文章讲解 视频讲解
- 时间复杂度 o(n)
- 空间复杂度 o(n)
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> set1, set2;vector<int> ans;for(int val : nums1) set1.insert(val);for(int val : nums2) set2.insert(val);for(int val : set1) {if(set2.count(val)) ans.push_back(val);}return ans;}
};
202.快乐数
题目链接 文章讲解
- 时间复杂度 o(logn) 计算方法暂时没有看
- 空间复杂度 o(logn)
class Solution {
public:bool isHappy(int n) {set<int> record;int ans = 0;while(true) {if (n) {int temp = n % 10;n = n / 10;ans += temp * temp;} else if (ans == 1) {return true;} else {if(record.count(ans)) return false;record.insert(ans);n = ans;ans = 0;}}}
};
1.两数之和
题目链接 文章讲解 视频讲解
下图来自官方题解下的评论:
- 时间复杂度 o(n)
注意：unordered_map的find()函数时间复杂度为o(1)，而map的find()时间复杂度为o(logn)，所以如果采用map总时间复杂度为o(nlong) - 空间复杂度 o(n)
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> record;for(int i = 0; i < nums.size(); ++i) {if(record.find(target - nums[i]) != record.end()) return { record[target - nums[i]], i }; record[nums[i]] = i;}return {}; }
};
