一、滑动窗口与双指针

滑动窗口

定长滑动窗口

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

1
2
3
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。

定长滑动窗口可以总结为以下几步：

1.将第i个元素入窗，更新相应的统计量。i < k - 1时重复这一步。

2.更新答案。（ans和temp取最大）。

3.将i - k + 1个元素出窗，更新相应的统计量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxVowels(char* s, int k) {
    int ans = 0;
    int temp = 0;
    for(int i = 0;i < strlen(s);i++) {
        if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
            temp++;
        }
        if(i < k - 1) {
            continue;   //先填满k-1个窗口，重复第一步
        }
        ans = ans > temp ? ans:temp;    //更新答案
        char out = s[i - k + 1];
        if(out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
            temp--;
        }   //出窗，更新统计量
    }
    return ans;
}

时间消耗特别大，找了一下原因，每次循环计算strlen导致时间复杂度退化为O(n^2)，应该用一个变量记录字符串长度。编程习惯惹的祸。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxVowels(char* s, int k) {
    int ans = 0;
    int temp = 0;
    int len = strlen(s);
    for(int i = 0;i <len;i++) {
        if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
            temp++;
        }
        if(i < k - 1) {
            continue;   //先填满k-1个窗口
        }
        ans = ans > temp ? ans:temp;
        char out = s[i - k + 1];
        if(out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
            temp--;
        }
    }
    return ans;
}

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

1
2
3
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。

这道题和上面的几乎一模一样，但是要注意的是我们ans的初始值要取的足够小，因为temp中间变量可能是负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
double findMaxAverage(int* nums, int numsSize, int k) {
    double temp = 0;
    double ans = -1.797693e+308;
    for(int i = 0;i < numsSize;i++) {
        temp += nums[i];
        if(i < k - 1) {
            continue;   //填满k-1个窗口
        }
        ans = ans > temp ? ans : temp; //更新最大值
        temp -= nums[i -k + 1];
    }
    return (ans / k);
}

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

1
2
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

这道题和上面的题基本一样，而且只需要中间变量即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int numOfSubarrays(int* arr, int arrSize, int k, int threshold) {
    int count = 0;
    int temp = 0;
    int aim = k * threshold;
    for(int i = 0;i < arrSize;i++) {
        temp += arr[i];
        if(i < k - 1) {
            continue;
        }
        if(temp >= aim) {
            count++;
        }
        temp -= arr[i - k + 1];
    }
    return count;
}

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

1
2
3
4
给你一个下标从 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 。

整体思想是一样的，但是要注意note和long long(commit后才反应过来)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getAverages(int* nums, int numsSize, int k, int* returnSize) {
    *returnSize = numsSize; //不知道是干啥，看了题解才知道要加这一句。
    int *ans = (int *)malloc(sizeof(int) * numsSize);
    memset(ans, -1, numsSize * sizeof(int));
    long long temp = 0;
    for(int i = 0;i < numsSize;i++) {
        temp += nums[i];
        if(i < 2 * k) {
            continue;
        }
        ans[i - k] = temp / (2 * k + 1);
        temp -= nums[i - 2 * k];
    }
    return ans;
}

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

1
2
3
4
给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。
给你一个整数 k ，表示想要 连续 黑色块的数目。
每一次操作中，你可以选择一个白色块将它 涂成 黑色块。
请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

这个问题可以转化成k大小的滑窗中W最少是多少。反应过来这个问题，答案就很简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minimumRecolors(char* blocks, int k) {
    //k大小滑窗中W最少有几个
    int temp = 0;
    unsigned int ans = -1;
    int len = strlen(blocks);
    for(int i = 0;i < len;i++) {
        if(blocks[i] == 'W') {
            temp++;
        }
        if(i < k - 1) {
            continue;
        }
        ans = ans < temp ? ans : temp;
        if(blocks[i - k + 1] == 'W') {
            temp--;
        }
    }
    return ans;
}

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

1
2
3
4
给你一个整数数组 nums 和两个正整数 m 和 k 。
请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
子数组指的是一个数组中一段连续 非空 的元素序列。

这道题要开一个hash来记录每个数字出现了多少次，如果是第一次出现，limit++，limit如果不超过m就不计算ans。元素出窗之后要将i-k+1元素的hash值减一，如果hash值变为0则代表这个元素已经不在滑窗中了，limit–。还有这道题的数据很大。

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
long long maxSum(int* nums, int numsSize, int m, int k) {
    int *hash = (int *)malloc(sizeof(int) * 1000000001);
    memset(hash, 0, sizeof(int) * 1000000001);
    long long temp = 0;
    long long ans = 0;
    int limit = 0;
    for(int i = 0;i < numsSize;i++) {
        if(hash[nums[i]] == 0) {
            limit++;
        }
        hash[nums[i]]++;
        temp += nums[i];
        if(i < k - 1) {
            continue;
        }
        if(limit >= m) {
            ans = ans > temp ? ans : temp;
        }
        temp -= nums[i - k + 1];
        hash[nums[i - k + 1]]--;
        if(hash[nums[i - k + 1]] == 0) {
            limit--;
        }      
    }
    free(hash);
    return ans;
}

lc.2461. 长度为 K 子数组中的最大和
和上一题一样，只不过窗口中的元素不能重复

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
long long maximumSubarraySum(int* nums, int numsSize, int k) {
    long long temp = 0;
    long long ans = 0;
    int count = 0;
    int *hash = (int *)malloc(sizeof(int) * 100001);
    memset(hash, 0, sizeof(int) * 10001);
    for(int i = 0;i < numsSize;i++) {
        if(hash[nums[i]] == 0) {
            count++;
        }
        hash[nums[i]]++;
        temp += nums[i];
        if(i < k - 1) {
            continue;
        }
        if(count < k) {
            temp -= nums[i - k + 1];
            if(--hash[nums[i - k + 1]] == 0) {
                count--;
            }
            continue;
        }
        else if(count >= k) {
            ans = ans > temp ? ans : temp;
        }
        temp -= nums[i - k + 1];
        if(--hash[nums[i - k + 1]] == 0) {
            count--;
        }
    }
    return ans;
}