hot100刷题记录

哈希

1、两数之和

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

• throw invalid_argument(“No result”);
  • 无结果报错
• mp.count(x)，判断x是否存在于mp里面

/*笔记
unordered_map 是什么？

unordered_map 是 哈希表（散列表）实现的键值对容器。
特点：

按 key 存取 value

查找 / 插入 / 删除平均时间复杂度 O(1)

无序（和 map 不同，map 是有序红黑树，O(log n)）

1. 头文件与定义
#include <unordered_map>
using namespace std;

unordered_map<int, int> mp;

含义：key 是 int，value 是 int

2. 常见初始化方式
空表
unordered_map<int, int> mp;
列表初始化
unordered_map<string, int> score = {
    {"Alice", 90},
    {"Bob", 85},
    {"Cindy", 95}
};
3. 插入元素（最常用）
方法1：[]
mp[1] = 100;
mp[2] = 200;

如果 key 不存在，会自动创建并赋值

如果 key 已存在，会覆盖旧值
方法2：insert
mp.insert({3, 300});
mp.insert(make_pair(4, 400));

不会覆盖已存在 key 的值（插入失败）

方法3：emplace（推荐）
mp.emplace(5, 500);

效率通常更好（原地构造）

4. 查找元素（重点）
方法1：find()（推荐）
auto it = mp.find(2);
if (it != mp.end()) {
    cout << "找到了，value = " << it->second << endl;
} else {
    cout << "没找到" << endl;
}
为什么推荐 find()？

因为它不会误创建元素。

方法2：count()
if (mp.count(2)) {
    cout << "存在 key=2" << endl;
}

对 unordered_map 来说，count(key) 只会是 0 或 1

5. 访问元素（重点坑）
mp[key]
cout << mp[10] << endl;

⚠️ 如果 key=10 不存在，会自动插入一项 {10, 0}（值类型默认构造）

这在做题时很容易造成 bug。

示例
unordered_map<int, int> mp;
cout << mp.size() << endl; // 0
cout << mp[100] << endl;   // 输出0，但同时插入了 key=100
cout << mp.size() << endl; // 1
安全读取：at()
cout << mp.at(2) << endl;

key 不存在会抛异常 out_of_range

不会自动插入

6. 修改元素
mp[1] = 999;   // 覆盖
mp.at(2) = 888; // key必须存在
7. 删除元素
按 key 删除
mp.erase(1);
按迭代器删除
auto it = mp.find(2);
if (it != mp.end()) {
    mp.erase(it);
}
清空
mp.clear();
8. 遍历方式
范围 for（最常用）
for (auto &p : mp) {
    cout << "key = " << p.first << ", value = " << p.second << endl;
}

p.first 是 key，p.second 是 value

迭代器遍历
for (auto it = mp.begin(); it != mp.end(); ++it) {
    cout << it->first << " " << it->second << endl;
}
9. 常用成员函数总结（刷题常用）
mp.size();       // 元素个数
mp.empty();      // 是否为空
mp.clear();      // 清空
mp.count(key);   // 是否存在（0/1）
mp.find(key);    // 查找，返回迭代器
mp.erase(key);   // 删除key
10. 你这个 two sum 里为什么用 unordered_map？

核心思想：
遍历到 nums[i] 时，先看 target - nums[i] 是否已经出现过。

unordered_map<int, int> mp; // 数值 -> 下标

for (int i = 0; i < nums.size(); ++i) {
    int need = target - nums[i];
    if (mp.count(need)) {
        return {mp[need], i};
    }
    mp[nums[i]] = i;
}
为什么先查再存？

避免同一个元素被重复使用（比如 target=6，nums[i]=3 时）。
12. 常见坑（很重要）
坑1：mp[key] 会自动插入
if (mp[100]) { ... }  // 这句可能悄悄插入 key=100

✅ 建议改为：

if (mp.count(100)) { ... }
坑2：遍历顺序不固定

unordered_map 是无序的，不要依赖输出顺序。

坑3：key 类型自定义时需要哈希函数

像 pair<int,int> 不能直接做 key（标准库默认没提供哈希），需要自定义 hash。
（你现在刷题先不用急，后面遇到我可以给你模板）
判断存在 + 取值
auto it = mp.find(key);
if (it != mp.end()) {
    // 存在
    int val = it->second;
}
计数统计
unordered_map<int, int> cnt;
for (int x : nums) {
    cnt[x]++;
}
分组（值是 vector）
unordered_map<int, vector<int>> groups;
for (int i = 0; i < nums.size(); ++i) {
    groups[nums[i]].push_back(i);
}

return

表示“正常结束函数”

返回一个结果

throw

表示“出现异常情况”

不返回正常结果，而是把错误抛出去

对比项	unordered_map	map
底层	哈希表	红黑树
是否有序	无序	按 key 升序
查找/插入/删除	平均 O(1)	O(log n)
适用场景	快速查找	需要有序遍历

49、字母异位词分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> mp;//一个哈希表，key是字符串，value是字母异位词
        for(string & str:strs){
                string key =str;
                sort(key.begin(),key.end());
                mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for(auto & p : mp){
            ans.emplace_back(p.second);
        }
        return ans;
    }
};

/*笔记
- for(auto & p : mp)可以迭代遍历，相当于for循环
- sort(string.begin(),string.end())可以对字符串内部进行排序
- emplace_back()
/*
emplace_back 的作用：在 vector 末尾“原地构造”一个元素（直接在容器内部创建），常用于提升效率、写法更顺。

1）最基本用法
vector<int> v;
v.emplace_back(5);   // 在末尾添加 5

这和下面几乎等价：

v.push_back(5);

对基础类型（int/double/string 这种）来说，两者差别通常不大。

2）它和 push_back 的核心区别
push_back(x)

先在外部构造好一个对象 x

再把它拷贝/移动进 vector

emplace_back(args...)

直接用参数 args... 在 vector 内部构造对象

少一次临时对象（可能更快）

3）为什么 emplace_back 常用于自定义类型（差别明显）

假设有个类：

struct Node {
    int a;
    string b;
    Node(int a, string b): a(a), b(std::move(b)) {}
};
用 push_back（会先构造临时对象再放进去）
vector<Node> v;
v.push_back(Node(1, "hi"));
用 emplace_back（直接在 vector 里构造）
vector<Node> v;
v.emplace_back(1, "hi");

emplace_back 更简洁，而且通常更省一次构造/移动。

4）回到你这题里的这句
mp[key].emplace_back(str);

mp[key] 是一个 vector<string>，所以这句等价于：

mp[key].push_back(str);

这里存的是 string，一般差别也不大，但 emplace_back 写法统一、习惯上常用。

5）一个你要注意的坑（重要）

如果你写：

v.emplace_back(str);

它会把 str 作为参数来构造末尾元素。
如果你写：

v.emplace_back(std::move(str));

就可能把 str 的内容“搬走”（移动语义），str 之后可能变空（可用但值不保证）。

在 LeetCode 这种场景通常不用 move，保持 str 不变更稳。

6）一句话记忆

push_back：把“已经存在的对象”放进去

emplace_back：用参数在容器里“直接生成一个对象”
/*
其实遍历 map 更常写成范围 for：

for (auto &p : mp) {
    ans.emplace_back(p.second);
}

p.first 是 key

p.second 是那组字符串

2、两数之和

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
      ListNode dummy(0);
      ListNode* cur=&dummy;
      int carry=0;
      while(l1!=nullptr || l2!=nullptr || carry){
            int x= (l1!=nullptr) ? l1->val: 0;
            int y=(l2!=nullptr)? l2->val:0;
            int sum=x+y+carry;
            carry=sum/10;
            int digit=sum%10;
            cur->next=new ListNode(digit);
            cur=cur->next;
            if(l1!=nullptr)l1=l1->next;
            if(l2!=nullptr)l2=l2->next;


      }
        return dummy.next;

    }
};

写法	dummy 是什么	是否真的创建节点	能否直接用 dummy.next / dummy->next
ListNode dummy(0);	节点对象	✅ 创建在栈上	用 dummy.next ✅
ListNode* dummy(0);	指针（nullptr）	❌ 没创建节点	dummy->next ❌ 会崩
ListNode* dummy = new ListNode(0);	指针	✅ 创建在堆上	dummy->next ✅

128、最长连续序列

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(),nums.end());
        int ans=0;
        for(int x : st){
            if(st.contains(x-1))
                continue;
            int y = x+1;
            while(st.contains(y))
                y++;

            ans=max(ans,y-x);

        }
        return ans;
    }
};

双指针

283、移动零

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0;
        for(int j = 0;j<nums.size();j++){
            if(nums[j]!=0){
                    nums[i]=nums[j];
                    if(i!=j)
                        nums[j]=0;
                    i++;


            }


        }
    }
};

11、盛最多水的容器

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l=0,r=height.size()-1;
        int res=0;
        while(l<r){
                 int area=(r-l)*min(height[l],height[r]);
                 res=max(area,res);
                if(height[l]<height[r])l++;
                else r--;
        }
        return res;
    }
};

15、三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        int n = nums.size();
        for(int i = 0;i<n-2;i++){
                if(i && nums[i]==nums[i-1])continue;
                if(nums[i]+nums[i+1]+nums[i+2]>0)break;
                if(nums[i]+nums[n-1]+nums[n-2]<0)continue;
                int j = i+1,k=n-1;
                while(j<k){
                        int s= nums[i]+nums[j]+nums[k];
                        if(s>0){
                            k--;
                        }
                        else if(s<0){
                            j++;
                        }
                        else{
                            ans.push_back({nums[i],nums[j],nums[k]});
                            for(j++;j<k&&nums[j]==nums[j-1];j++);
                            for(k--;j<k&&nums[k]==nums[k+1];k--);

                        }


                }
        }
        return ans;
    }
};

42、接雨水

class Solution {
public:
    int trap(vector<int>& height) {
       int n = height.size();
       int left=0,right=n-1;
       int pre_max=0,bakc_max=0;
       int ans=0;
       while(left<right){
            pre_max=max(pre_max,height[left]);
            bakc_max=max(bakc_max,height[right]);
            ans+= pre_max<bakc_max? pre_max-height[left++]:bakc_max-height[right--];



       }
       return ans;
    }
};

滑动窗口

3、无重复字符的最长字串

技巧

136、只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }
};