05 August 2008
给定一个整数数组 nums 和一个整数 k，返回总和至少为 k 的 nums 的最短非空子数组的长度。如果没有这样的子数组，则返回 -1。
子数组是数组的连续部分。
TreeMap+Prefix Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
TreeMap<Long, Integer> tp = new TreeMap();
public int shortestSubarray(int[] nums, int k) {
long prefixSum = 0;
tp.put(Long.valueOf(0), -1);
int min = nums.length + 1;
for (int i = 0; i < nums.length; i++) {
prefixSum += nums[i];
Long key = tp.floorKey(prefixSum - k);
while(key!=null){
min = Math.min(min, i - tp.get(key));
if (min == 1) {
return 1;
}
tp.remove(key);
key = tp.lowerKey(key);
}
tp.put(prefixSum, tp.getOrDefault(prefixSum, i));
}
return (min == nums.length + 1) ? -1 : min;
}
}
Monotonic Queue Solution with Space Optimization on Prefix Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
Deque<long[]> dq = new ArrayDeque<long[]>();
dq.offer(new long[]{-1,0});
int i = 0;
long curSum = 0;
int res = Integer.MAX_VALUE;
while(i < nums.length)
{
curSum += nums[i];
while(!dq.isEmpty() && dq.peekFirst()[1] <= curSum - k) res = Math.min(res, (int)(i - dq.pollFirst()[0]));
while(!dq.isEmpty() && dq.peekLast()[1] >= curSum) dq.pollLast();
dq.offerLast(new long[]{i, curSum});
i++;
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}