算法(数组)——滑动窗口_滑动窗口数组

---

1.长度最小的子数组

1.1题目实例(中等)

    给定一个含有 n 个正整数的数组和一个正整数 target 。
    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
1
2
3
4
5
6
7
8
9
10
11
12

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum

1.2解题思路

    这里考虑利用前后两个指针覆盖若干连续的元素构成一个滑动窗口，通过前后指针的移动，不断根据要求调整窗口内的元素个数，调整整个窗口在数组中的位置。那么现在有几个要点需要考虑：

• 前指针什么时候前移，使滑动窗口向前延伸？
• 后指针什么时候前移，使滑动窗口收缩屁股？
      开始，滑动窗口内的元素个数应该先增加，直到元素的和大于等于target的时候，再考虑后指针的移动，并且此时要记录滑动窗口的大小，此时是sum第一次达到target。
      接下来后指针要前移，在sum依然大于等于target的情况下，不断更新滑动窗口的大小，记录最小值。直到sum<target的时候，再次时前指针前移，直到sum>=target的时候，再像之前一样考虑后指针的移动。

1.3代码实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;   //定义result为最大32位整数
        int backIndex = 0;
        int sum = 0;
        for( int frontIndex = 0; frontIndex < nums.size(); frontIndex ++)
        {
            sum += nums[frontIndex];
            while(sum >= target)//元素和满足target要求后考虑后指针的移动
            {
                int length = frontIndex - backIndex + 1;//计算滑动窗口大小
                result = length < result ? length : result;//令result等于result和length中较小的一个
                sum -= nums[backIndex ++];
            }
        }
         return result == INT32_MAX ? 0 : result;//result未被重新赋值的话返回0
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.水果成篮(中等)

2.1题目实例

    你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
    你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
    你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
    一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
    给你一个整数数组fruits, 返回你可以收集的水果的最大数目。

示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fruit-into-baskets

2.2解题思路

    同样使用滑动窗口的办法来进行解答，定义两个左右指针，让右指针去遍历数组。每当右指针指向一个新的元素的时候，会出现以下几种情况。

• 之前的窗口里还没有元素，也即没有采摘任何一种水果。
• 之前的窗口已经有了一种元素，也即采摘到了一种水果。
• 之前的窗口已经有了两种元素，即两种水果都采摘了。

    针对以上三种情况，需要分别作出以下应对：

• 将第一种水果种类赋值为右指针所指元素，记录其位置。
• 将第二种水果种类赋值为右指针所指元素，记录其位置。
• 查询右指针最左边元素的种类，此种类和右指针所指的新种类即为新的两种水果，根据之前的记录将被排除的水果种类从窗口中移除。

2.3代码实现

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int rightIndex = 0, leftIndex = 0;
        int typeCnt1 = -1, typeCnt2 = -1;//记录水果的种类
        int size = fruits.size();
        int maxLength = 0, tmpLength = 0;
        int lastIndex1 = 0,lastIndex2 = 0; //记录每一种水果的最后索引位置
        for(; rightIndex < size; rightIndex++)
        {
            if(typeCnt1 == -1 && fruits[rightIndex] != typeCnt2)
            {
                typeCnt1 = fruits[rightIndex];
                lastIndex1 = rightIndex;
                tmpLength = rightIndex - leftIndex + 1;
                maxLength = tmpLength > maxLength ? tmpLength : maxLength;
                continue;
            }
            if(typeCnt2 == -1 && fruits[rightIndex] != typeCnt1)
            {
                typeCnt2 = fruits[rightIndex];
                lastIndex2 = rightIndex;
                tmpLength = rightIndex - leftIndex + 1;
                maxLength = tmpLength > maxLength ? tmpLength : maxLength;
                continue;
            }
            if(fruits[rightIndex] == typeCnt1)
            {
                lastIndex1 = rightIndex;
            }
            else if(fruits[rightIndex] == typeCnt2)
            {
                lastIndex2 = rightIndex;
            }
            else//出现第三种水果，要进行水果种类的更换
            {
                if(fruits[rightIndex - 1] == typeCnt1)//右指针最左边一个水果是typeCnt1，则该水果保留，移动窗口使水果TypeCnt2被移除
                {
                    leftIndex = lastIndex2 + 1;
                    typeCnt2 = fruits[rightIndex];
                    lastIndex2 = rightIndex;
                }
                else
                {
                    leftIndex = lastIndex1 + 1;
                    typeCnt1 = fruits[rightIndex];
                    lastIndex1 = rightIndex;
                }
            }
            tmpLength = rightIndex - leftIndex + 1;
            maxLength = tmpLength > maxLength ? tmpLength : maxLength;
        }
        return maxLength;
    }
};
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55