定长滑动窗口-基础题

难度依次从高到低

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

给你字符串 s 和整数 k 。

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

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

#define max(a,b) ( (b) > (a) ? (b) : (a))   // 利用宏定义处理简单函数
int maxVowels(char* s, int k) {
    int ans=0,vowel=0;              // ans为最大值，vowel为目前值
    for(int i=0; s[i]; i++) {
        // 1. 左指针的处理
        if( s[i] == 'a' || s[i] == 'e'  || s[i] == 'o' || s[i] == 'i' || s[i] == 'u') {
            vowel++;
        }
        if(i < k-1 ) {
            continue;
        }
        // 2.更新答案
        ans = max(ans,vowel);
        // 子串若均为元音则跳出循环
        if (ans == k) break;
        // 3.左指针的处理
        char left = s[i - k + 1];
        if(left == 'a' || left == 'e' || left == 'i' || left == 'o' || left == 'u') {
            vowel--;
        }
    }
    return ans;
}

class Solution {
public:
    int maxVowels(string s, int k) {
        int ans = 0;
        int curr = 0;
        for(int i = 0; i < s.size(); i++) {
              if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
                curr++;
            }
            int left = i - k + 1;
            if(left < 0) {
                continue;
            }
            ans = max (ans, curr);
            if(ans == k) break;
            char out = s[left];   // 出去的是元音，则需要-1
             if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
                curr--;
            }
        }
        return ans;
    }
};

依旧是构造滑动窗口，出去的时候若是元音则减去，进来的时候则加上，获取最大值。

# 643.子数组最大平均数 I

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

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

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

#define max(a, b) ((b) > (a) ? (b) : (a))
double findMaxAverage(int* nums, int numsSize, int k) {
    int s = 0;                           // 当前窗口的元素和
    int max_sum = INT_MIN;                     // 最大值
    for( int right = 0 ; right < numsSize ; right++ ) {
        s += nums[right];
        if( right < k - 1 ) {
            continue;
        }
        max_sum = max(max_sum, s);
        int left = ( right - k + 1);
        s -= nums[right - k + 1];
    }
    return (double) max_sum / k;
}

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int left = 0;
        int ans = INT_MIN, curr = 0;
        for(int right = 0; right < nums.size(); right++) {
            curr += nums[right];
            if(right < k -1 ) continue;
            ans = max(curr,ans);
            curr -= nums[left++];
        }
        return ans*1.0 / k;
    }
};

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

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

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

int numOfSubarrays(int* arr, int arrSize, int k, int threshold) {
    int right = 0;
    int compare=threshold*k;        //平均值转化为和
    int sum = 0;
    int num = 0;                    
    for(right=0; right<arrSize; right++) {
        sum += arr[right];
        if(right < k-1) continue;
        if(sum >= compare)num++;
        int left = right - k + 1;
        sum -=arr[left];
    }
    return num;
}

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int ans = 0, curr = 0, sum = threshold * k;
        int left = 0;
        for(int right = 0; right < arr.size(); right++) {
            curr += arr[right];
            if(right < k -1) continue;
            if(curr >= sum) ans++;
            curr -= arr[left++];
        }
        return ans;
    }
};

# 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 。
int* getAverages(int* nums, int numsSize, int k, int* returnSize) {
    *returnSize = numsSize;
    int* ave = malloc(numsSize * sizeof(int));
    memset(ave, -1, numsSize * sizeof(int)); // 初始化为 -1
    long long sum = 0;
    int num = 0; 
    for (int right = 0; right < numsSize; right++) {
        sum += nums[right];
        if (right < k * 2) {
            continue;
        }
        ave[right - k] = sum / (k * 2 + 1);
        sum -= nums[right - k * 2];
    }
    return ave;
}
class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        int windows = 2 * k + 1;
        long long  curr = 0; 
        int left = 0;
        vector<int> ans(nums.size(),-1);
        for(int right = 0; right < nums.size(); right++) {
            curr += nums[right];
            if( right - left + 1 ==  windows) {
                ans[left + k ] = curr / windows;
                curr -= nums[left++];
            }
        }
        return ans; 
    }
};
窗口不再是k，反而是2k+1，开局设置所有默认为-1，然后再进修改值

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

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

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

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

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

int minimumRecolors(char* blocks, int k) {
    int len= strlen(blocks);
    int now_window=0,max_window=0;            // 当前窗口的黑块数量和记录窗口的最大黑块数量
    for( int right=0; right < len; right++) {
        if(blocks[right] == 'B') now_window++;    // 右指针指向黑方块，则now_window++
        if(right< k - 1) continue;
        if(max_window < now_window) max_window = now_window;
        int left =right - k + 1;
        if(blocks[left] == 'B') now_window--;
    }
    return k-max_window;
}

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int curr = 0, ans = INT_MAX, left =0;
        for(int right = 0; right < blocks.size(); right++) {
            if(blocks[right] == 'W') curr++;
             if(right >= k - 1) {
                ans = min(ans, curr);
                if(blocks[left++] == 'W') curr--;
            }
        }
        return ans;
    }
};

求最小次数，使用min比较，记得把ans初始化成INT_MAX即可

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

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

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

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

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

#define max_size 20000
#define max(a, b) ((a) > (b) ? (a) : (b))
typedef struct {
    int value[max_size];                   // 数组中的关键字
    int key[max_size];                     // 数组中关键字出的次数
    int size;                              // 哈希表不同元素的个数
}Hashmap;
// 初始化哈希表
void init_Hashmap(Hashmap* map) {  
    map->size=0;                             // 哈希表目前零个元素
    memset(map->key,0,sizeof(map->key));     // 初始化
    memset(map->value,0,sizeof(map->value)); // 初始化
}
// 插入操作
void insert_Hashmap (Hashmap* map, int val) {
    // for循环检查是否有相同元素
    for(int i = 0; i <map->size; i++){
        if(map->key[i] == val) {
            map->value[i]++;                //计数器+1
            return;
        }
     }
    // 没有相同元素的操作
    map->key[map->size] = val;             // 加入该关键字
    map->value[map->size] = 1;             // 计算器+1
    map->size++;                           // 哈希表有的元素+1
   
}
void remove_Hashmap(Hashmap* map,int val) {
    // for循环找到去除的元素进行—1操作
    for(int i = 0; i<map->size; i++){
        if(map->key[i] == val){
            map->value[i]--;
            // 如若溢出的元素仅有一个，那么将最右边的函数放到这个位置上，使得哈希表紧凑
            if(map->value[i] == 0){
                map->key[i] = map->key[map->size-1];
                map->value[i]=map->value[map->size-1];
                map->size--;
            }
            return;
        }
    }
}
// 检查哈希表中有多少不同元素
int different_numbers(Hashmap* map, int m) { 
    return map->size >= m;        // 返回判断后的结果
    }

long long maxSum(int* nums, int numsSize, int m, int k) {
    long long ans = 0, max = 0;
    Hashmap map;
    init_Hashmap(&map);
    // 滑动窗口固定操作
    for(int right = 0; right < numsSize; right++) {
        insert_Hashmap(&map,nums[right]);
        max += nums[right];
        if(right < k-1) continue;
        if(different_numbers(&map, m)) ans = max(ans, max);
    long long left =nums[right - k + 1];
    remove_Hashmap(&map, left);
    max -= nums[right - k + 1];
    }
    return ans;
}

class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        unordered_map<int,int> cnt;
        long long curr = 0, ans = 0;
        for(int right = 0; right < nums.size(); right++) {
            curr += nums[right];
            cnt[nums[right]]++;
            if(right - k + 1 < 0) continue;
            if( cnt.size() >= m) {
                ans = max(ans, curr);
            }
            curr -= nums[right - k + 1];
            if(--cnt[nums[right - k + 1]] == 0) cnt.erase(nums[right - k + 1]);
        }
        return ans;
    }
};

哈希表的容量作为当前窗口内的元素数量，用erase去除即可

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

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

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

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

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

#define N 100001
#define max(a,b) a>b?a:b
long long maximumSubarraySum(int* nums, int numsSize, int k) {
    long long ans = 0,sum = 0;
    int hash[N] = { 0 };
    int cnt = 0;
    for(int right=0; right<numsSize; right++){
        sum += nums[right];
        if(++hash[nums[right]] == 2){
            cnt++;
        }
        if(right < k - 1) continue;
        if(cnt == 0) {
            ans = max(ans,sum);
        }
        int left = right - k + 1;
        if(--hash[nums[left]] == 1) cnt--;
        sum -= nums[left];
    }
    return ans;
}

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        long long curr = 0, ans = 0;
        unordered_map<long long, int>cnt;
        for(int right = 0; right < nums.size(); right++) {
            curr += nums[right];
            cnt[nums[right]]++;
            if(right < k - 1) continue;
            if(cnt.size() == k ) ans = max(ans,curr);
            int left = right - k + 1;
            curr -= nums[left];
            if(cnt[nums[left]] == 1) cnt.erase(nums[left]);
            else cnt[nums[left]]--;
        }
        return ans;
    }
};

本题和上题的区别是，上题可以有重复，而这题则是不可以重复。

# 1423.可获得的最大点数

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

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

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

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

#define min(a,b) a>b?b:a 
int maxScore(int* cardPoints, int cardPointsSize, int k) {
    int windows = 0, right = 0, sum = 0, ans = INT_MAX;
    if(k == cardPointsSize){
        for(right = 0; right < cardPointsSize; right++){
            sum += cardPoints[right];
        }
        return sum;
    }
    for(right = 0; right < cardPointsSize; right++){
        windows += cardPoints[right];
        sum += cardPoints[right];
        if(right < cardPointsSize - k -1) continue;
        ans = min(ans,windows);
        int left = right -(cardPointsSize - k -1 );
        windows -= cardPoints[left];
    }
    return sum-ans;
}

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int ans = INT_MAX, curr =0, sum = 0, left = 0;
        int windows_size = cardPoints.size() - k;
        if( windows_size == 0) return accumulate(cardPoints.begin(), cardPoints.end(), 0);
        for(int right = 0; right < cardPoints.size(); right++) {
            sum += cardPoints[right]; // 计算总和
            curr += cardPoints[right];
            if(right -left + 1 < windows_size) continue;
            ans = min(curr, ans);
            curr -= cardPoints[left++];
        }
        return sum - ans;
    }
};

求头部或尾部取卡的最大值，那么就是求窗口内最小值

accumulate为计算函数。

算法 leetcode