遇到continous subarray的题目,最常用的策略就是构建累加和preSum数组.这样,此题就转化为在preSum中找到两个间距最短的位置j和i,使得preSum[j]-preSum[i]>=K.对于这种题,通常我们会遍历i,然后在每个i之前的index查找满足条件的最小j.
对于此类问题,我们会把所有经历过的preSum都存在一个有序集合里.这里我们使用map,记录曾经出现过的preSum以及它对应的在数组中的index.注意到如果遇到相同的preSum,后加入的index会覆盖先前的值,这是合理的:因为对于任何preSum我们恰需要更新的,较大的index来保持[j,i]之间的距离最短.
假设我们考虑某个i,那么在i之前出现的所有preSum都已经在map里.此时如果map里所有键小于preSum[i]-K的preSum都是符合要求的.我们只要遍历这些键对应的值(也就是index),找到最大的那个就是距离i最近的j.
这样的算法仍然会超时,主要是因为上面遍历键值的过程花时间.怎么优化呢?
我们每次在将{preSum[i],i}插入map时,插入的可能是map中间的某个位置.我们发现,此时所有大于preSum[i]的键都是没有意义的,因为你preSum[i]带来了当前最新(也是最大)的值i.举个例子,如果此时目标键为k且k>preSum[i],那么在map中搜索所有小于等于k的"键"并且找它们之中最大的"值",得到的结果必然是i.所以每个回合里,我们插入{preSum[i],i}之后,可以将map从后往前不断删除元素,直至遇到preSum[i]为止,这样可以使得map始终保持精简.
上面这个操作会带来一个意想不到的好处!那就是我们不需要找在map里遍历所有小于等于preSum[i]-K的所有键并求最大的值．因为这些"键"对应的最大"值"就存在于离preSum[i]-K最近的那个键里面．更本质的原因是，map里不仅键是递增的，而且对应的值也是递增的．
所以每个回合的过程可以总结为:
1.在map里找到小于并且离preSum[i]-K最近的那个键,其值就是所需的满足条件的最大j
2.在map里插入{preSum[i],i}
3.在map删除所有大于preSum[i]的键
上述的解法复杂度是o(NlogN),但实际上还有更好的o(N)的解法．
我们维护一个双端队列q，里面存储的q[j]表示的是一个递增的index的序列．同时要保证presum[q[j]]也是递增的．是不是有点绕？
假设我们现在处理A[i]，其对应的前缀和是presum[i]，那么我们想在这个队列里面找到一个位置j，恰好使得presum[q[j]]+K<=presum[i]，那么队列中的q[0]~q[j]这些index都是满足at least K条件的位置，我们可以找其中最大的一个，比如说q[j']，就能使得subarray长度i-q[j']是最小的．接下来的操作很重要，我们可以将q[0]到q［j']都从队列前端弹出．因为以后的i会更大，如果它在队列中找到的满足at least K条件的左边界位置比q[j']小的话，不会比已经得到的result更好．所以任何早于q[j']的队列元素对以后的搜索都没有帮助．
接下来，我们需要将presum[i]的信息加入这个队列．我们的策略是不断在后端弹出元素，直到presum[q.back()]<presum[i]，即保证这个队列对应的presum依然是递增的．这个比较好理解，和解法１的道理一样．因为当前的i是最靠后，那么所有队里中已有的presum大于presum[i]的元素都是没有意义的，完全可以被i取代（即依然保证at least K同时能使subarray更短）．
所以每次处理一个presum[i]时，遵循上述两个步骤，就能保证队列存储的是一个递增的index序列，而且对应的presum也是递增的．