Leetcode 209. 长度最小的子数组（小白学习之路）

蔚落 2023-07-15 13:07 2阅读 0赞

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbnQyeXg0_size_16_color_FFFFFF_t_70][]

这个题目一开始我没有看清题目中要求是“**连续**”的子数组，因此最早想到的方法是讲整个数组排序，如果最大的数满足>=s,则输出1，最大加第二大的数满足，则输出2.遇到这个测试用例时报错

s = 213, \[12,28,83,4,25,26,25,2,25,25,25,12\]

明确题意后，首先想到的方法是1.暴力法，两个指针，遍历几乎所有情况，代码如下：

class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) { 
            int slow=0,fast=0, minlen=10000,templen=255;    //一个慢指针一个快指针
            for(;slow<nums.size();slow++)     //慢指针从0开始
            {
                int sum=0;    //每开始一个慢指针，重置当前的和为0
                for(fast=slow;fast<nums.size();fast++)    //快指针从慢指针开始往后加
                {
                    sum+=nums[fast];
                    if(sum>=s)    //满足要求
                    {
                        templen = fast- slow + 1;    //当前长度计算
                        if(templen<minlen) minlen=templen;     //如果小于最小长度，更新。这两行可以用一行min函数的代码搞定
                    }
                }
            }
            if(templen==255) return 0;    //没有满足要求的情况，返回
            else return minlen;    
    
        }
    };

看了下官方题解说的暴力法，时间复杂度有O（n3），我这种暴力法应该属于改良过的，时间复杂度应该只有O(n2)，测试结果从执行用时上看很惨淡，说明肯定有更好的方法；

第二种方法2.滑动窗口法

这种方法算法课上老师有提到过，这次终于碰到实战应用，写了一下确实很快，总的来说就是一前一后双指针，形成了一个方框，所有的数加起来后如果<s,说明不存在满足要求的数组，返回0；如果总和>=s,则加左指针可使总和减小，在此期间探到最小的数组长度，代码如下：

class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int left = 0, right = 0, sum = 0, minlen = 10000;
            while (left < nums.size()&& right<nums.size())
            {
                if (sum >= s)     //总和大于S的情况，左指针右移
                {
                    minlen = min(minlen, right - left);
                    sum -= nums[left];
                    left++;
                }
                else    //总和小鱼S的情况，右指针右移
                {
                    sum += nums[right];  //先加右指针的数再把右指针右移，因此右指针属于开区间
                    right++;
                }
    
            }
            while (sum >= s&&left<nums.size())    //由于右指针开区间，存在越界风险，这里讨论的是已经加到最后一位的情况
            {
                minlen = min(minlen, right - left);
                sum -= nums[left];
                left++;
            }
            if (minlen == 10000) return 0;
            else return minlen;
    
        }
    };

这里的代码可以再简洁一点就是如果先加nums\[right\]再right++的话就不用担心right越界的情况

还有第3中方法叫二分查找法，引进了一个新的sum数组，第i个数表示nums数组前i项的和，该方法我个人认为比较复杂，将找最小数组的问题转为找一个临界值的问题，从而可以用常用的更快的查找方法来加快速度，这里就不写了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbnQyeXg0_size_16_color_FFFFFF_t_70]: /images/20230528/8c7a529319f149499c9bd7070ee26baf.png