回顾一下之前做的哈希，貌似只有用到
unordered_set：存储无序元素unordered_map：存储无序键值对
1.两数之和5/5【30min】
1.set和map分不清，set是只有值，map是键值对。
2、map的键值弄反了，找数的话，键是数，值是索引i
3.考虑如果有重复的数怎么办：不要提前把数组转成map，一边遍历一边转。
class Solution {
//考虑输入
public:
vector<int> twoSum(vector<int>& nums, int target) {
//快速判断一个元素是否出现集合里
//如果是哈希，怎么存数据
//没考虑一样的元素
// unordered_set<int> mySet;
// for(int i= 0;i<nums.size();i++){
// mySet.insert(target - nums[i]);
// }
// for(int i= 0;i<nums.size();i++){
// auto iter = mySet.find(nums[i]);
// if(iter!=mySet.end()){
// continue;
// }
// return {i,*iter};
// }
unordered_map<int,int>findmap;//快速找下标
//有重复的怎么办
for(int i = 0;i<nums.size();i++){
auto it = findmap.find(target-nums[i]);
if(it != findmap.end()){
return {i,it->second};
}
findmap[nums[i]] = i;//索引和值反了
}
return {};
}
};2 字母异位词分组【30min】
map和set的区别，map是键值对，set是只有值，vector和set的区别是？？？
unordered_set/map比set/map用的多的原因是O(1)????
const string&使用引用避免拷贝【如果是不操作这个对象，可以省点空间，否则就创建了新对象】
语法问题：
// ❌ 错误代码
for (auto it : mp) { // it是键值对的拷贝，不是迭代器！
result.push_back(it->second); // 错误：it不是指针/迭代器
}// ✅ 修正代码
for (const auto& entry : mp) { // entry是键值对的引用
result.push_back(entry.second); // 正确：用 . 访问成员
}
anto it = mp.find("a")这里it是指针
for(auto it : mp)这里it是一个对象，访问pair的键or值需要用点（.）it.second
问题：1.string的sort函数怎么用：有一个strs:sort(strs.begin(),strs.end())
2.键和值怎么考虑，这里其实不需要find
3.一对多的处理：1个sort后的string对应多个string怎么办：string对应vector<string>【妙】
4.string的初始化，有一个string a,则string b = a;
5.迭代器是指针还是对象，见上
6.想了一下一对多怎么处理，原来想用multiset,find(key) 返回指向 第一个匹配键 的元素的迭代器，可以用equal_range，放后，以后看。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
//tae和tea如何等价
//如何处理输入输出
//按次序排列？
//先字符串排序，转成一样的用map存。然后find，键：原，值：改后的字符串
vector<vector<string>>result;
// unorder_map<string,string> word;//有重复怎么办，如果multi_map有重复find返回什么
//z这个不用find了，直接遍历:键：改后的字符串；值：原
unordered_map<string,vector<string>>mp;
for(const auto &it:strs){//这里it是数组
// string newOne = sort(it.begin(),it.end());
string newOne = it;
sort(newOne.begin(),newOne.end());
mp[newOne].push_back(it);//*it?
}
for(const auto &it:mp){
result.push_back(it.second);
}
return result;
}
};#include <iostream>
#include <map>int main() {
std::multimap<int, std::string> mmap = {
{1, "A"}, {1, "B"}, {2, "C"}, {1, "D"}
};// 方法1：使用 find
auto it = mmap.find(1);
if (it != mmap.end()) {
std::cout << "First match: " << it->second << std::endl; // A
}// 方法2：使用 equal_range
auto range = mmap.equal_range(1);
std::cout << "All values for key 1:\n";
for (auto it = range.first; it != range.second; ++it) {
std::cout << " " << it->second << std::endl; // A, B, D
}// 方法3：使用 lower_bound 和 upper_bound
std::cout << "All values for key 1 (via bounds):\n";
auto lower = mmap.lower_bound(1);
auto upper = mmap.upper_bound(1);
for (auto it = lower; it != upper; ++it) {
std::cout << " " << it->second << std::endl; // A, B, D
}return 0;
}
3.最长连续序列[7min]
无序数组，找到最长连续序列，第一反应是动态规划的最长子序列hhhh
错误：1.没考虑两个数相等的情况：continue，跳出本层循环，进下一层。
2.max和count的初始值刚开始是0，不合理，应该是1，因为就算没有长的序列，一个数也是1【类似最长公共子序列】
3.这就引出一个问题，输入[]，输出是0：关注边界值。
--------------------------------人都傻了：快排是O(nlogn)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
//字连续的最长序列（不要求序列元素在原数组中连续）的长度。
//sort(O(logn))
if(nums.size()==0){
return 0;
}//[]:0
sort(nums.begin(),nums.end());
int max = 1;//[0]:0
int count = 1;
for(int i = 0;i<nums.size();i++){
if(i == nums.size()-1){
break;
}
if(nums[i] == (nums[i+1]-1)){
count++;
}else if(nums[i] == nums[i+1]){
continue;
}else{
count = 1;
}
if(count>=max){
max = count;
}
}
return max;
//[1,0,1,2]
}
};符合题目要求版本【见下】：想法妙在：把找连续子序列的问题转换为找连续子序列第一个值是谁的问题
不过对时间复杂度还是有点迷惑，确实最坏达不到O(n^2)，又是多少呢 ：O(n)，每个元素最多被访问两次（一次插入集合，一次遍历处理）【比如234589,2会进入while，然后找到345,345会continue;8会进入while，9会被find；所以每个元素最多只被遍历两次】
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
//快排是O(nlogn)
//一般：找x-1,x-2,x+1,x+2...-->找这个连续序列的第一个数，找到之后遍历得到整个序列长度
//如何确定max
unordered_set<int>s;
if(nums.size()==0){
return 0;
}
for(int i = 0;i<nums.size();i++){
s.insert(nums[i]);
}
// int start;
int maxNum = 1;
for(int current:s){//遍历只遍历不重复的即unordered_set里的，78测试用例过了
int a = 1;//本轮max
// int current = s[i];
if(s.find(current-1)!=s.end()){
continue;
}else{
// start = i;
while(s.find(current+1)!=s.end()){
a++;
current++;//忘记了
}
}
maxNum = max(maxNum,a);
}
// for(int i = 0;i<nums.size();i++){
// //怎么找这个连续序列
// }
return maxNum;
}
};