和至少为K的最短子数组

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K

如果没有和至少为 K 的非空子数组，返回 -1 。

示例 1：

输入：A = [1], K = 1
输出：1

示例 2：

输入：A = [1,2], K = 4
输出：-1

示例 3：

输入：A = [2,-1,2], K = 3
输出：3

1 <= A.length <=
50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9

这道题的关键在于我们要知道各个区间的和。从而来判断哪个区间的和是满足要求的。用暴利解法逐个判断是可行的，但是耗费的时间太多。因为暴力解法其实做了很多重复的工作。那么为了节省重复的计算，有个方法就是保存数组的前缀和数组。也就是用一个数组sum来记录各个区间的和。也就是

sum[i]=arr[0]+arr[1]+……+arr[i-1]。这里为了计算方便，增加了以为sum[0]=0。有了这个数组，就可以很方便的求解任意区间的和。

比如要求区间[4,6]的和，就可以用sum[6]-sum[4]。

那么接下来的工作就是要将sum数组中的各个求和值入队列。

(1) 当区间[0,i]的值比[0,i-1]的值要大的时候，就直接进队列。

(2) 当区间[0…i]的值比区间[0….i-1]还要小的时候，那么对于后面的位置，其实可以忽略掉i-1，因为sum[n]-sum[i] > sum[n]-sum[n-1]。也就是[i,n]区间的值比[i-1,n]的值要大，而且更短。因此i-1这个位置就可以被踢出队列。

比如队列里面的数值如下：0,1,3,5,4。由于4比5小，此时应该将5剔除出队列，为什么呢，如果保留5在队列里面，当后面一个数组比如7进队列的时候，队列数组变成0,1,3,5,4,7。这个时候计算区间和7-5明显比7-4要小。而且[5,7]的区间长度为2，[4,7]的区间长度为1。因此5没有必要存在于队列中。队里中的值变为0,1,3,4,7

每次完成队列插入的操作后，就要开始对队列里面的区间进行计算了。

当队列为0,1的时候，1-0<4 不满足条件

当队列为0,1,3的时候，3-1<4 不满足条件

当队列为0,1,3,5的时候，5-0>4 满足条件，最小长度为3。0出队列，队列变为1,3,5
继续比较5-1>4,最小长度为2,1出队列，队列变为3,5。

当队列为3,4的时候(由于5比4小，因此出队列), 4-3<4不满足条件

当队列为3,4,7的时候，7-3>=4，满足条件，最小长度为2

代码如下：

没有采用队列或者栈的结构，就用数组来存储dquue，用dq_begin, dq_end, dq_size来分别表示数组的第一个，最后一个元素以及数组长度。

int shortestSubarray(int a[], int k, int len)

{

int *dqueue;

int *sum;

int
i,dq_begin,dq_end,dq_size,min_length,lengh;

dqueue = (int *)malloc((len + 1) * sizeof(int));

sum = (int *)malloc(len * sizeof(int));

memset(sum, 0,len * sizeof(int));

memset(dqueue, 0, (len + 1) * sizeof(int));

dq_begin = 0;

dq_end = -1;

dq_size = 0;

min_length = len+1;

for (i = 1; i
<= len; i++)

{

*(sum + i) = *(sum+i-1)+a[i-1];

}

for (i = 0; i
<= len; i++)

{

if (i != 0)

{

while (dq_size > 0 && sum[dq_end] >= sum[i])

{

dq_end -= 1;

dq_size -= 1;

}

while (dq_size > 0 && sum[i] - sum[dq_begin] >= k)

{

lengh = i - dq_begin;

min_length = min_length >=
lengh ? lengh : min_length;

dq_begin += 1;

dq_size -= 1;

}

dq_end += 1;

dqueue[dq_end] = i;

dq_size += 1;

}

return min_length;

}

巴特西

和至少为K的最短子数组

最新文章

热门文章