力扣hot100刷题记录

目录

哈希

关于哈希，以下是记忆模板：

unordered_map<Key类型, Value类型> mp;

// 存
mp[key] = value;

// 统计
mp[key]++;

// 查
if (mp.find(key) != mp.end()) {
    // 存在
}

// 遍历
for (auto& pair : mp) {
    pair.first;   // key
    pair.second;  // value
}

还有一个unordered_set：一个“只存唯一值”的无序集合，而且查找非常快。用法：

#include <unordered_set>
using namespace std;

unordered_set<int> st;

#插入
st.insert(5);
#判断是否存在
if (st.count(5)){}
#删除
st.erase(5);
#集合大小
st.size();

1.两数之和

链接

数组中找两个数，使它们满足某个和

优先使用哈希表：

unordered_map<int, int> mp;

for (...) {
    int need = target - nums[i];

    if (mp.find(need) != mp.end())
        return {mp[need], i};

    mp[nums[i]] = i;
}

2.字母异位词分组

链接

把具有相同特征的元素分组

这题的“特征”就是：排序后的字符串

unordered_map<特征, vector<原元素>> mp;

for (原元素) {
    特征 = 计算特征;
    mp[特征].push_back(原元素);
}

3.最长连续序列

链接

找连续数字，但原数组本身是乱序的。

核心就一句：找不到前驱，才开始往后找。

要求 O(n) → unordered_set。
num - 1 不存在 → num 才是连续序列起点。
从起点不断检查 num + 1。
每段只扫描一次，所以整体 O(n)。

unordered_set<int> st(nums.begin(), nums.end());

for (int num : st) {

    // 只有前一个数字不存在，才是起点
    if (st.find(num - 1) == st.end()) {

        int current = num;
        int length = 1;

        while (st.find(current + 1) != st.end()) {
            current++;
            length++;
        }
    }
}

双指针

1.移动零

int slow = 0;

for (int i = 0; i < nums.size(); i++) {
    if (满足保留条件) {
        nums[slow] = nums[i];
        slow++;
    }
}

2.盛最多水的容器

两端选两个位置 + 求最大面积 + 宽度和高度互相制约

优先想到双指针：

int left = 0, right = n - 1;

while (left < right) {
    更新答案;

    if (左边更矮)
        left++;
    else
        right--;
}

3.三数之和

sort(nums.begin(), nums.end());

for (int i = 0; i < n - 2; i++) {
    // i 去重

    int left = i + 1;
    int right = n - 1;

    while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];

        if (sum < target)
            left++;
        else if (sum > target)
            right--;
        else {
            记录答案;
            左右去重;
        }
    }
}

4.接雨水

while (left < right) {

    if (height[left] < height[right]) {
        leftMax = max(leftMax, height[left]);
        ans += leftMax - height[left];
        left++;
    }
    else {
        rightMax = max(rightMax, height[right]);
        ans += rightMax - height[right];
        right--;
    }
}

滑动窗口

1.无重复字符的最长子串

最长/最短连续子串 + 满足某个条件，优先考虑 滑动窗口。

unordered_set<char> window;

int left = 0;

for (int right = 0; right < s.size(); right++) {

    while (当前窗口不合法) {
        删除 s[left];
        left++;
    }

    加入 s[right];

    更新答案;
}

2.找到字符串中所有字母异位词

在字符串中找所有长度固定、字符频率满足条件的子串，优先想到：固定长度滑动窗口 + 频率数组

for (int right = 0; right < s.size(); right++) {

    加入 s[right];

    if (窗口太长) {
        删除 s[left];
        left++;
    }

    if (窗口满足条件) {
        记录 left;
    }
}

子串

1.和为 K 的子数组

连续子数组 + 子数组和等于某个值 → 前缀和 + 哈希表。

unordered_map<int, int> mp;
mp[0] = 1;

int sum = 0, ans = 0;

for (...) {
    sum += ...;
    ans += mp[sum - k];
    mp[sum]++;
}

2.滑动窗口最大值

连续长度 k 的窗口，每移动一步求最大/最小值 → 单调队列 + 存下标

deque<int> q;

q.push_back(2);   // [2]        从后面加入2
q.push_back(3);   // [2, 3]     从后面加入3
q.push_front(1);  // [1, 2, 3]  从前面加入1

cout << q.front(); // 1         查看第一个元素
cout << q.back();  // 3         查看最后一个元素

q.empty() == true   // q 是空的
q.empty() == false  // q 里面有元素

while (!q.empty() && nums[q.back()] <= nums[i]){
    q.pop_back();
}

3.最小覆盖子串

过

普通数组

1.最大子数组和

curSum = max(nums[i], curSum + nums[i]);
maxSum = max(maxSum, curSum);

2.合并区间

一堆区间，要合并重叠区间

sort(intervals.begin(), intervals.end());

for (...) {
    if (当前左端点 > 上一个右端点)
        加入新区间;
    else
        更新右端点为 max(...);
}

3.轮转数组

k %= n;

reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());

4.除了自身以外数组的乘积

int left = 1;
for (int i = 0; i < n; ++i) {
    answer[i] = left;
    left *= nums[i];
}

int right = 1;
for (int i = n - 1; i >= 0; --i) {
    answer[i] *= right;
    right *= nums[i];
}

5.缺失的第一个正数

先略过

矩阵

1.矩阵置零

vector<bool> row(m,false);
vector<bool> col(n,false);

for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
        if(matrix[i][j]==0){
            row[i]=true;
            col[j]=true;
        }
    }
}
for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
        if(row[i]||col[j]){
            matrix[i][j]=0;
        }
    }
}

2.螺旋矩阵

while (top <= bottom && left <= right) {
    上边 → top++;
    右边 → right--;
    if (...) 下边 → bottom--;
    if (...) 左边 → left++;
}

3.旋转图像

// 转置
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        swap(matrix[i][j], matrix[j][i]);

// 每行反转
for (int i=0;i<n;i++)
    reverse(row.begin(), row.end());