算法

力扣hot100(精讲一)

说明

  • 我这里写个是为了做一下整理
  • 我觉得有趣，如果开发累了，可以换一换脑子
  • 注：题目可直抵题目，所以不写题目内容

题目讲解[哈希+双指针+滑动窗口+子串+普通数组+矩阵]

哈希：快速映射和快速查找

两数之和

  1. 暴力法 暴力法就是遍历所有数，然后两两相加，如果和等于目标值，则返回结果，否则返回-1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    vector<int> twoSum(std::vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};
  1. 哈希表
  • 哈希表就是将数组中的数作为键，索引作为值，然后遍历数组，将每个数作为键，索引作为值，如果哈希表中存在目标值，则返回结果，否则返回-1
  • 时间复杂度：O(n) 为什么可以优化时间呢？

    因为哈希表的查找时间杂度是 O(1)，而数组的查找时间复杂度是 O(n)，所以哈希表可以提高查找效率。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    vector<int> twoSum(std::vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int,int>mp;
        for(int i=0;i<n;i++){
            if(mp.find(target-nums[i])!=mp.end()){
                return {i,mp[target-nums[i]]};
            }
            mp[nums[i]]=i;
        }
        return {};
    }
};

字母异位词分组

  • 思路：哈希表，将字符串排序，作为键，将原字符串作为值，然后遍历字符串，将排序后的字符串作为键，将原字符串作为值，如果哈希表中存在目标值，则返回结果，否则返回-1
  • 时间复杂度：O(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>>m;
        for(string& s:strs){
            string s1=s;
            sort(s1.begin(),s1.end());
            m[s1].push_back(s);
        }

        vector<vector<string>>ans;
        ans.reserve(m.size());
        for(auto & [x,value]:m){
            ans.push_back(value);
        }
        return ans;
    }
};

最长连续序列

  • 思路:因为是O(n)所以是不能用排序，所以要用不能用排序，要用unordered_set的特性 先来去重，然后在用.count() 去查找计数
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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.count(x-1)){
                continue;
            }
            int now=x;
            int cnt=1;
            while(st.count(now+1)){
                now++；
                cnt++;
            }
            ans=max(ans,cnt);
        }
        return ans;
    }
}

双指针

移动零

  • 思路：双指针，一个指针指向当前位置，一个指针指向下一个位置，如果当前位置为0，则将下一个位置的值赋给当前位置，然后将下一个位置指针后移一位，直到下一个位置为0，然后将当前位置指针后移一位，直到数组末尾
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int l=0,r=1;
        if(nums.size()==1) return;
        while(r<nums.size()){
            if(nums[l]!=0){
                l++;
            }
            if(nums[l]==0){
                if(nums[r]!=0){
                    swap(nums[l],nums[r]);
                    l++;
                }
            }
            r++;
        }
    }
};

盛最多水的容器

  • 思路：贪心+双指针 这题往双指针方向想很正常，问题在于怎么让矩形更大（x*y） 贪心在：面积 = min(左高, 右高) × (右索引 - 左索引)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

三数之和

  • 思路：三个数和双指针，那怎么办？=>先排序后固定一个数（b + c = -a），O(n2) 重点：不能全局去重改变数组 。三个数都要做去重
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

接雨水

  • 网红题目,不必多言据说字节的扫地阿姨都会做

  • 我的思路：其实我不理解为什么说难看一个柱子能接多少水，应该就能想到贪心+双指针/单调栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int trap(vector<int>& height) {
        int lmax=0,rmax=0;
        int l=0,r=height.size()-1;
        int n=height.size();
        int ans=0;
        while(l<r){
            lmax=max(lmax,height[l]);
            rmax=max(rmax,height[r]);
            if(lmax>rmax) {
                ans+=rmax-height[r];
                r--;
            }
            else{
                ans+=lmax-height[l];
                l++;
            }
        }
        return ans;
    }
};

滑动窗口

无重复字符的最长子串 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l=0;
        unordered_map<char,int>mp;
        int ans=0;
        for(int i=0;i<s.length();i++){
            char c=s[i];
            mp[c]++;
            while(mp[c]>1){
                mp[s[l]]--;
                l++;
            }
            ans=max(ans,i-l+1);
        }
        return ans;
    }
};

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

  • 暴力写法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        sort(p.begin(), p.end());
        vector<int> ans;
        int len = p.size();
        int n = s.size();
        for (int l = 0; l + len <= n; l++) {
            string res = s.substr(l, len);
            sort(res.begin(), res.end());
            if (res == p) {
                ans.push_back(l);
            }
        }
        return ans;
    }
};
  • 滑动窗口
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        vector<int>cnt1(26,0);
        vector<int>cnt2(26,0);
        int len=p.size();
        for(int i=0;i<p.size();i++){
            cnt1[p[i]-'a']++;
        }

        for(int r=0;r<s.size();r++){
            cnt2[s[r]-'a']++;
            int l=r-len+1;
            if(l<0) continue;
            if(cnt1==cnt2) ans.push_back(l);
            cnt2[s[l]-'a']--;
        }
        return ans;
    }
};

子串

和为 K 的子数组

*思考过程：前缀和+哈希

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int>sum(n+1);
        for(int i=0;i<nums.size();i++){
            sum[i+1]=sum[i]+nums[i];
        }
        int ans=0;
        unordered_map<int,int>mp;
        mp[0]=1;
        for(int i=1;i<=n;i++){
            if(mp.find(sum[i]-k)!=mp.end()) ans+=mp[sum[i]-k];
            mp[sum[i]]++;
        }
        return ans;
    }
};

滑动窗口最大值

*单调队列版子，没什么好说的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int>q;
        vector<int>ans;
        for(int i=0;i<nums.size();i++){
            while(!q.empty()&&nums[q.back()]<nums[i]) q.pop_back();
            q.push_back(i);
            if(i>=k-1)//窗口长度为k，因为是从0开始，所以i-k+1为窗口的起始位置
            {
                while(!q.empty()&&q.front()<=i-k) q.pop_front();
                ans.push_back(nums[q.front()]);
            }
        }
        return ans;
    }
};

最小覆盖子串 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include<bits/stdc++.h>
class Solution {
public:
    string minWindow(string s, string t) {
        int n=s.size();
        int m=t.size();
        unordered_map<char,int>cnt_n,cnt;
        for(auto &x:t) cnt_n[x]++;
        int l=0,r=0;
        int need=0;
        int mi=INT_MAX;
        int st=0;
        while(r<n){
            char c=s[r++];
            if(cnt_n.count(c)){
                cnt[c]++;
                if(cnt[c]==cnt_n[c]) need++;
            }
            while(need==cnt_n.size()){
                if(r-l<mi){
                    st=l;
                    mi=r-l;
                }
                char d=s[l++];
                if(cnt_n.count(d)){
                    if(cnt[d]==cnt_n[d]) need--;
                    cnt[d]--;
                }
            }
        }
        return mi==INT_MAX?"":s.substr(st,mi);
    }
};

数组

最大子数组和 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int>dp(nums.size());
        dp[0]=nums[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(nums[i],dp[i-1]+nums[i]);
        }
        return *max_element(dp.begin(),dp.end());
    }
};

合并区间 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// (要维护的)
//num[0][1]>nums[1][0]  3>2
//nums[0][0]<nums[1][0] 1<2
//比较 nums[0][1] 和 nums[1][1]
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        vector<vector<int>>ans;
        for(auto & p:intervals){
            if(!ans.empty()&&p[0]<=ans.back()[1]){
                ans.back()[1]=max(ans.back()[1],p[1]);
            }
            else ans.push_back(p);
        }
        return ans;
    }
};

轮转数组 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k=k%n;
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

除了自身以外数组的乘积 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int>pre(n,1);
        vector<int>suf(n,1);
        for(int i=1;i<n;i++){
            pre[i]=pre[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--){
            suf[i]=suf[i+1]*nums[i+1];
        }
        vector<int>ans(n);
        for(int i=0;i<n;i++){
            ans[i]=pre[i]*suf[i];
        }
        return ans;
    }
};

缺失的第一个正数

时间复杂度O(n)，空间是O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> s;
        for (int num : nums) {
            if (num >0&&num<=n) {
                s.insert(num);
            }
        }
        int res=1;
        while(s.count(res)) res++;
        return res;
    }
};

仔细思考一下，最大可能是n+1,最小是1,可以假设是最大情况，最后发现第一个不符合题意的就是ans;

  • for 跑 n 次，while 每次跑 n 次 → n×n = O (n²)，这是不对的，实际上只会交换n次，时间复杂度是O(n)

这是并行次数，不是嵌套次数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            while(nums[i]>=1&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){
                swap(nums[i],nums[nums[i]-1]);
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1) return i+1;
        }
        return n+1;
    }
};

矩阵

矩阵置零 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size();int n=matrix[0].size();
        vector<bool>a(m);
        vector<bool>b(n);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]==0){
                    a[i]=b[j]=1;
                }
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(a[i]==1||b[j]==1) matrix[i][j]=0;
            }
        }
    }
};

螺旋矩阵 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int l=0,r=matrix[0].size()-1;
        int top=0,bottom=matrix.size()-1;
        vector<int>ans;
        while(1){
            //左到右
            for(int i=l;i<=r;i++){
                ans.push_back(matrix[top][i]);
            }
            top++;
            if(top>bottom) break;

            //上到下
            for(int i=top;i<=bottom;i++){
                ans.push_back(matrix[i][r]);
            }
            r--;
            if(l>r) break;

            //右到左
            for(int i=r;i>=l;i--){
                ans.push_back(matrix[bottom][i]);
            }
            bottom--;
            if(top>bottom) break;

            //下到上
            for(int i=bottom;i>=top;i--){
                ans.push_back(matrix[i][l]);
            }
            l++;
            if(l>r) break;
        }
        return ans;
    }
};

旋转图像 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(i==j) continue;
                swap(matrix[i][j],matrix[j][i]);
            }
        }
        for(int i=0;i<n;i++){
            reverse(matrix[i].begin(),matrix[i].end());
        }
    }
};

搜索二维矩阵 II 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int top=0;
        int r=matrix[0].size()-1;
        while(top<=matrix.size()-1&&r>=0){
            if(matrix[top][r]==target){
                return true;
            }
            else if(matrix[top][r]>target){
                r--;
            }
            else if(matrix[top][r]<target){
                top++;
            }
        }
        return false;
    }
};
© 2025 - 2026 acye
使用 Hugo 构建
本站访客： 人 · 总访问量： 次