[LeetCode]Shortest Subarray with Sum at Least K

首先这道题没有办法用普通的双指针做，因为随着首尾两个指针的移动，子数组的和不是单调地变化的，所以我们没有办法每次移动右边的指针之后再移动左边的指针找到size最小的subarray。类似地，binary search之类的做法也是不行的，比如我们验证存不存在长度为i的子数组和大于等于K，假如不存在的话，我们没有办法决定是增大下界还是缩小上界，因为长度更小的subarray的和可能更大。所以我们要思考其他的方法，我们可以观察出几个特点：

1. presum[i]表示从0到i的前缀和，如果对于i < j，presum[i] >= presum[j]的情况，显然对于j之后的index k。如果presum[k] - presum[i]大于等于K，那么因为presum[k] - presum[j] >= presum[k] - presum[i]，所以presum[k] - presum[j]必定也满足条件而且[j + 1, k]这个区间比[i + 1, k]更短
2. 对于j > i，如果j是满足presum[j] - presum[i] >= K的最小值。那么对于k > j，我们不需要考虑presum[k] - presum[i]了，因为即使区间和大于K也比[i +1, j]要长

所以这给了我们一个类似于Sliding Window Maximum的思路，如果我们维护一个递增的前缀和的序列s，对于我们所在的当前index i:

1. 如果这个序列的尾巴对应前缀和s.back() >= presum[i]，我们pop_back()。对应上面的情况1，我们不需要考虑其作为区间起始位置的情况，因为i是永远比它更优的起始位置。
2. 如果这个序列的头对应的前缀和满足presum[i] - s.front() >= K，pop_front()，更新最小区间，对应情况2。已经pop出来的都将其作为区间起始位置考虑过并且存在某个以其为起始的区间大于等于K，还在序列s之中的都是其作为区间开头不满足在扫过的index中存在某个以它开始的区间，其区间和大于等于K。

同时需要在序列的头和尾进行pop的操作，我们选择deque来实现。时间复杂度为O(n)，显而易见每个元素进出队列一次，空间复杂度O(n)。代码如下：

	class Solution {
	public:
	int shortestSubarray(vector<int>& A, int K) {
	int len = A.size(), presum = 0, res = INT_MAX;
	deque<pair<int, int>> dq;
	dq.emplace_back(0, -1);
	for(int i = 0; i < len; ++i)
	{
	presum += A[i];
	while(dq.size() && dq.back().first >= presum)dq.pop_back();
	while(dq.size() && presum - dq.front().first >= K)
	{
	res = min(res, i - dq.front().second);
	dq.pop_front();
	}
	dq.emplace_back(presum, i);
	}
	return res == INT_MAX? -1: res;
	}
	};

view raw Shortest Subarray with Sum at Least K.cpp hosted with ❤ by GitHub