[数据结构与算法]Leetcode 862. 和至少为 K 的最短子数组（DAY 192）---- 滑动窗口好题（恢复算法状态中）

原题题目

代码实现（首刷自解 968ms）

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        deque<long> deque;
        unordered_map<long,int> map;

        int ret = INT_MAX,size = nums.size();
        long long sum = 0;
        deque.emplace_back(0);
        map[0] = -1;
        for(int i=0;i<size;++i)
        {
            sum = sum + static_cast<long>(nums[i]);
            long num = k - sum;
            if(deque.size())
            {
                auto iter = lower_bound(deque.begin(),deque.end(),num);
                if(iter != deque.end())
                {
                    int pos = iter-deque.begin();
                    ret = min(ret,i-map[deque[pos]]);
                }
                iter = lower_bound(deque.begin(),deque.end(),-sum);
                deque.erase(deque.begin(),iter);
            }
            map[-sum] = i;
            deque.emplace_front(-sum);
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

代码实现（首刷 大部分看解 滑动窗口）

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        deque<int> deque;
        vector<long> presum(nums.size()+1,0);
        int ret = INT_MAX;
        for(int i=0;i<nums.size();++i)
            presum[i+1] = nums[i] + presum[i];
        
        for(int i=0;i<presum.size();++i)
        {
            while(!deque.empty() && presum[i] <= presum[deque.back()])    deque.pop_back();
            while(!deque.empty() && presum[i] - presum[deque.front()] >= k)
            {
                ret = min(ret,i-deque.front());
                deque.pop_front();
            }
            deque.emplace_back(i);
        }

        return ret == INT_MAX ? -1 : ret;
    }
};