Leetcode 862. 和至少为 K 的最短子数组

写在前面:

算法小白，想通过每日一题+博客记录的形式来督促自己提升，在此过程中肯定会有诸多问题，欢迎各位大佬批评指正，我们山顶见！！

---------------------------------------------------------------------------------------------------------------------------------

正文开始：

题目：

   给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

示例：

思考过程：

      题意理解：   将一个连续的子数组中的每一个元素相加，若结果等于k，则返回这样的子数组的最短长度，若无这样的非空子数组，则返回-1；

       题中出现连续的子数组相加，则考虑用前缀和方法处理初始数据。

        n=nums.size();
        vector<int>s(n+1,0);
        for (int i = 1; i <= nums.size(); i++)
        {
            s[i] = s[i-1] + nums[i-1];
        }

先创建一个长度为n(nums.size())+1的数组s，初始化为0；

小问答：为何为n+1呢？

               因为前缀和数组是s[i]=s[i-1]+nums[i-1];

               当i=1时，s[1]=s[0]+nums[0];所以若s的长度=nums长度+1

此时s[i]-s[j]=nums[j+1]++.....+nums[i] 我们想要的子数组模型不就出来了嘛；

当s[i]-s[j]>=k时不就是我们要的答案嘛？ 但这是理想化的，因为这个nums数组可能有正有负，s可能是一个不单调的数组，

若is[j] 若s[t]-s[i]可以>=k那s[t]-s[j]同样也可以>=k；

减数越小，差值越大

且j是距离t更近的数，是一个更优的解，所以我们更需要的是这个j而不是这个i；

需要将之前存入的i（因为i

根据我们的需求来看，我们需要定义一个双端队列来处理这个问题；

         deque<int> de;
        de.push_back(0);

小问答：

       为什么需要push_back（0）；

       因为初始化队列，让接下来的相减有一个初始的减数

此时de队列第一个数为0

 while (de.size() && s[i] <= s[de.back()])
                de.pop_back();

若is[j] 若s[t]-s[i]可以>=k那s[t]-s[j]同样也可以>=k；

减数越小，差值越大，且j是距离t更近的数，是一个更优的解，所以我们更需要的是这个j而不是这个i，同时也为了让比较的队列成为单调递增的队列

需要将之前存入的i（因为i思考下为什么？

接下来完成我们题解最重要的一步进行条件判断

       当s[i]-s[队列中的第一个数]>=k时，我们先更新一下最优解，之后再将队列中的第一个数移除

      为什么要将第一个数移除呢？

       因为s[i]-s[first]已经满足了条件，之后的队列都不会用到first了，当i增加时他已经不需要去跟first比较，因为相减就算满足条件，这时候也不是最优解。我们没必要再去用到它

 while (de.size()&&s[i]-s[de.front()]>=k)
            {
                ans = min(ans,i-de.front());
                de.pop_front();
            }

做完这一切之后，我们将刚刚的i插入到我们的单调队列de中

            de.push_back(i);

至此我们的函数主体已经讲完，具体实现如下

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k)
    {
        int n=nums.size();
        int ans=n+1;
        vector<long long> s(n+1,0);
        for (int i = 1; i <= n; i++)
        {
            s[i] = s[i-1] + nums[i-1];
        }
        deque<int> de;
        de.push_back(0);
        for(int i=1;i<=n;i++)
        {
            while (de.size()&&s[i]-s[de.front()]>=k)
            {
                ans = min(ans,i-de.front());
                de.pop_front();
            }
            while (de.size() && s[i] <= s[de.back()])
                de.pop_back();
            de.push_back(i);
        }   
        return ans==n+1?-1:ans;
    }
};

 本文代码及思想参考：【力扣（LeetCode） 每日一题 单调队列 862. 和至少为 K 的最短子数组 - 2022-10-26】

‘克拉克黎明之前’大佬对我的帮助很大，本文仅以记录学习为目的，无任何其他想法，若侵权可联系我删除

——————————————————————————————————————————

写在后面：

第一篇真正意义的博客至此结束了，本来我认为写博客完全没啥意义，但在完成这一篇的过程中，发现很多之前自己没有考虑到的问题，在这过程中学到了很多。因为是第一篇博客，在排版，语言等方面还略显青涩，请多多包涵。未来我也会在博客方面多多提升自己，争取产生出更多优质内容，一起进步，我们山顶见！