文章目录
- 题目链接
- 题目
- 思路
- 前缀和
- 暴力法
- 优化一
- 优化二
- 另一种写法
题目链接
https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/
题目
思路
https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/solution/liang-zhang-tu-miao-dong-dan-diao-dui-li-9fvh/
前缀和
定义前缀和s[0]=0s[0]=0s[0]=0,s[i+1]=∑j=0inums[j]s[i+1]=\sum\limits_{j=0}^{i}nums[j]s[i+1]=j=0∑inums[j]
例如,nums = [1,2,-1,2],对应的前缀和数组为s=[0,1,3,2,4]
通过前缀和,我们可以把子数组的和转换成两个前缀和的差,即
∑j=leftrightnums[j]=∑j=0rightnums[j]−∑j=0leftnums[j]=s[right+1]−s[left]\sum\limits^{right}_{j=left}nums[j]=\sum\limits^{right}_{j=0}nums[j]-\sum\limits^{left}_{j=0}nums[j]=s[right+1]-s[left]j=left∑rightnums[j]=j=0∑rightnums[j]−j=0∑leftnums[j]=s[right+1]−s[left]
例如,nums的子数组[2,-1,2]的和就可以用s[4]-s[1]=4-1=3,这时,right=3,left=1
注意:
为了方便计算,常用左闭右开区间[left,right)来表示子数组,此时子数组的和为s[right]-s[left],子数组的长度为right-left
暴力法
求出nums的前缀和s后,可以用暴力法,枚举所有的i>j且s[i]-s[j]>=k的子数组[j,i),取其中最小的i-j作为答案
import java.util.Arrays;class Solution {public int shortestSubarray(int[] nums, int k) {int[] prefixSum = new int[nums.length + 1];prefixSum[0] = 0;for (int i = 1; i < prefixSum.length; i++) {prefixSum[i] = prefixSum[i - 1] + nums[i - 1];}int arrLen = Integer.MAX_VALUE;for (int i = 1; i < prefixSum.length; i++) {for (int j = 0; j < i; j++) {if (prefixSum[i] - prefixSum[j] >= k) {arrLen = Math.min(arrLen, i - j);}}}return arrLen == Integer.MAX_VALUE ? -1 : arrLen;}
}
暴力法的时间复杂度是O(n2)O(n^2)O(n2)
可以在遍历前缀和s数组的时候,同时用某个合适的数据结构来维护遍历过的s[i],并即时移除无用的s[i]
优化一
遍历到s[i]时,考虑左边的某个s[j],如果s[i]-s[j]>=k,那么无论s[i]右边的数字是大是小,都不可能把j当作子数组的左端点,得到一个比i-j更短的子数组。因此s[j]没有任何作用了
优化二
如果s[i]<=s[j],加入后续有数字x能和s[j]组成满足要求的子数组,即x-s[j]>=k,那么必然也有x-s[i]>=k,由于从s[i]到x这段数组更短,因此s[j]没有任何作用了
做完这两个优化后,再把s[i]加到这个数据结构中
由于优化二保证了数据结构中的s[i]会形成一个递增序列,因此优化一移除的是序列最左侧的若干元素,优化二移除的是序列最右侧的若干元素。我们需要一个数据结构,它支持移除最左端的元素和最右端的元素,以及在最右端添加元素,故选用双端队列
由于双端队列的元素始终保持单调递增,因此这种数据结构也叫做单调队列
另一种写法
在计算前缀和的同时去计算答案,这需要在双端队列中额外存储前缀和的值
由于前缀和的初始值0在遍历nums之前就算出来了,因此需要在遍历之前,往双端队列中插入前缀和0及其下标-1
关于-1的解释
因为上面遍历的是s,下面遍历的nums,两者的下标偏移了一位
import java.util.LinkedList;class Solution {public int shortestSubarray(int[] nums, int k) {int res = Integer.MAX_VALUE;LinkedList<Pair> q = new LinkedList<>();q.add(new Pair(0L, -1));long curS = 0L;for (int i = 0; i < nums.length; i++) {curS += nums[i];//优化一while (!q.isEmpty() && curS - q.getFirst().key >= k) {res = Math.min(res, i - q.pollFirst().value);}//优化二while (!q.isEmpty() && q.getLast().key >= curS) {q.pollLast();}q.add(new Pair(curS, i));}return res == Integer.MAX_VALUE ? -1 : res;}class Pair {Long key;Integer value;public Pair() {}public Pair(Long key, Integer value) {this.key = key;this.value = value;}}
}