这是我学习算法入门用以记录的博客，记录了对应的leetcode题目及我的code，错误原因及改进分析

参考灵茶山艾府大神的文章

一、定长滑动窗口

image-20250725104701364

核心思想：

对于定长滑窗问题，在滑动过程中无需重新遍历整个窗口空间，而只考虑移除部分和添加部分

  • 窗口右端口在ii时，由于窗口长度为kk，所以窗口左端点为i−k+1i-k+1
  • 总结为三个步骤：进-更新-出：
    • 入：下标为ii的元素进入窗口，更新相关统计量。如果窗口左端点i−k+1<0i-k+1<0，即i<k−1i<k-1，则尚未进入第一个窗口，重复第一步
    • 更新：更新答案。一般都是更新最大值/最小值
    • 出：下标为i−k+1i-k+1的元素离开窗口，更新相关统计量，为下一次循环做准备

1456.定长子串中元音的最大数目

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

mycode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> vowels = {'a','e','i','o','u'};
        int n = s.size();
        int res = 0;
        for(int i=0;i<n-k+1;i++){
            int ans = 0;
            for(int j=i;j<i+k;j++){
                if(vowels.count(s[j])) ans++;
            }
            res = max(res,ans);
        }
        return res;
    }
};

采用了暴力枚举所有子串的方法，时间复杂度是O(nk)O(nk)

在过样例时卡在了第103个，是一个n和k均非常大的样例，导致直接爆了

改进code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> vowels = {'a','e','i','o','u'};
        int n = s.size();
        int res = 0;
        for(int i=0;i<k;i++){
            if(vowels.count(s[i])) res ++;
        }
        int ans = res;
        for(int i=0;i<n-k+1;i++){
            if(vowels.count(s[i])) ans--;
            if(vowels.count(s[i+k])) ans++;
            res = max(res,ans);
        }
        return res;
    }
};

过了，但是耗时还是挺高的

643.子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案

mycode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double res = 0;
        for(int i=0;i<k;i++){
            res += nums[i];
        }
        double ans = res/k;
        for(int i=0;i<nums.size()-k;i++){
            res -= nums[i];
            res += nums[i+k];
            ans = max(ans,res/k);
        }
        return ans;
    }
};

跟上一题差不多

1343.大小为 K 且平均值大于等于阈值的子数组数目

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

mycode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int count = 0;
        int sum = 0;
        for(int i=0;i<k;i++){
            sum += arr[i];
        }
        if(sum >= threshold*k) count ++;
        for(int i=0;i<arr.size()-k;i++){
            sum += arr[i+k];
            sum -= arr[i];
            if(sum >= threshold*k) count ++;
        }
        return count;
    }
};

2090.半径为 k 的子数组平均值

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。

半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。

构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。

x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。

  • 例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

mycode

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:
    vector<int> getAverages(vector<int>& nums, int k) {
       vector<int> ans(nums.size());
       long long sum = 0;
       if(nums.size()<2*k+1) return vector<int>(nums.size(),-1);
       for(int i=0;i<k;i++){
            ans[i] = -1;
            ans[nums.size()-1-i] = -1;
       } 
       for(int i=0;i<2*k+1;i++){
            sum += nums[i];
       }
       ans[k] = sum/(2*k+1);
       for(int i=k+1;i<nums.size()-k;i++){
            sum += nums[i+k];
            sum -= nums[i-k-1];
            ans[i] = sum/(2*k+1);
       }
        return ans;
    }
};

一开始sum定义了整型，然后就整数溢出了，换成了long long

改进

学习一些不一样的写法，比如sum的计算可以直接：

1
long long sum = accumulate(nums.begin(),nums.begin()+k*2+1,0LL);

还有不需要像上面那样先写个循环初始化一个窗口，参考灵神的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
public:
    vector<int> getAverages(vector<int>& nums,int k){
        int n = nums.size();
        vector<int> avgs(n,-1);
        long long s = 0;// 维护窗口元素和
        for(int i=0;i<n;i++){
            // 1.进入窗口
            s += nums[i];
            if(i<2*k){ // 窗口大小不足 2k+1
                continue;
            }
            // 2.记录答案
            avgs[i-k] = s/(k*2+1);
            // 3.离开窗口
            s -= nums[i-k*2];
        }
        return avgs;
    }
}

2379.得到 K 个黑块的最少涂色次数

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

mycode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int count = INT_MAX;
        int res = 0;
        int n = blocks.size();
        for(int i=0;i<k;i++){
            if(blocks[i]=='W') res++;
        }
        if(!res) return 0;
        count = min(res,count);
        for(int i=0;i<n-k;i++){
            if(blocks[i]=='W') res--;
            if(blocks[i+k]=='W') res++;

            count = min(res,count);
        }
        return count;
    }
};

2841.几乎唯一子数组的最大和

给你一个整数数组 nums 和两个正整数 m 和 k 。

请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。

如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。

子数组指的是一个数组中一段连续 非空 的元素序列。

mycode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        long long maxsum = 0,sum = 0;
        int n = nums.size();
        unordered_map<int,int> cnt;
        for(int i=0;i<n;i++){
            cnt[nums[i]]++;
            sum += nums[i];
            if(i<k-1) continue;

            int left = i-k+1;
            if(cnt.size()>=m) maxsum = max(maxsum,sum);
            sum -= nums[left];
            if(cnt[nums[left]] == 1) cnt.erase(nums[left]);
            else cnt[nums[left]]--;
        }
        return maxsum;
    }
};

2461.长度为 K 子数组中的最大和

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

  • 子数组的长度是 k，且
  • 子数组中的所有元素 各不相同 。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组 是数组中一段连续非空的元素序列。

mycode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        long long maxsum = 0, sum = 0;
        for(int i=0;i<nums.size();i++){
            cnt[nums[i]]++;
            sum += nums[i];

            int left = i-k+1;
            if(left < 0) continue;

            if(cnt.size()==k){
                maxsum = max(maxsum,sum);
            }

            cnt[nums[left]]--;
            sum -= nums[left];
            if(cnt[nums[left]]==0) cnt.erase(nums[left]);
        }
        return maxsum;
    }
};

1423.可获得的最大点数

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

mycode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        long long maxsum = 0 , sum = 0 , total = 0;
        int n = cardPoints.size();
        for(int i=0;i<n;i++) total += cardPoints[i];
        if(n==k) return total;
        for(int i=0;i<n;i++){
            sum += cardPoints[i];
            int left = i-(n-k)+1;
            if(left < 0) continue;

            maxsum = max(maxsum,total-sum);
            
            sum -= cardPoints[left];

        }
        return maxsum;
    }
};

改进

total的求和部分用reduce

1
total = reduce(cardPoints.begin(),cardPoints.end())

发现，时间复杂度下去了

1052.爱生气的书店老板

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。

mycode

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 maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int maxsum = 0,sum = 0;
        int n = customers.size();
        for(int i=0;i<n;i++){
            maxsum += customers[i]*(1-grumpy[i]);
        }
        sum = maxsum;
        for(int i=0;i<n;i++){
            if(grumpy[i] == 1) sum += customers[i];

            int left = i-minutes+1;
            if(left < 0) continue;

            maxsum = max(maxsum,sum);

            if(grumpy[left] == 1) sum -= customers[left]; 
        }
        return maxsum;
    }
};