当前位置:   article > 正文

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

滑动窗口数组


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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/676694
推荐阅读
相关标签
  

闽ICP备14008679号