题目描述
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其和 ≥ target
的长度最小的 连续子数组 ,并返回其长度。如果不存在符合条件的子数组,返回 0
。
样例1
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
样例2
输入:target = 4, nums = [1,4,4]
输出:1
样例3
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
提示
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
算法1
(前缀和 + 二分)
- 我们需要找到一个长度尽可能短的连续子数组,使得$S_i - S_j >= target$,即$S_j <= S_i - target$,要想使得$S_i - S_j$尽可能小,必须找到最大的满足条件的$S_j$。由于数组中全是正数,所以前缀和单调递增,可以通过二分来查找小于等于$S_i - target$的最大$S_j$,数组长度为
i - j
- 为了避免从头开始的子数组被考虑到,需要添加一个哨兵防止特判。
- 不用显式定义出前缀和数组,可以一边遍历一边统计
- 时间复杂度:$O(n \log n)$
- 空间复杂度:$O(n)$
Java 代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
TreeMap<Integer,Integer> map = new TreeMap<>();
int sum = 0, res = Integer.MAX_VALUE;
map.put(0, -1);
for(int i = 0; i < n; i++){
sum += nums[i];
Integer k = map.floorKey(sum - target);
if(k != null){
int j = map.get(k);
res = Math.min(res, i - j);
}
map.put(sum, i);
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
算法2
(双指针)
- 由于数组没有负数,随着
i
的递增,j
单调不减,可以通过双指针进行扫描数组:- 枚举每个
i
,如果i
和j
所指向的区间满足条件,则把j
往前移动,直到把数组缩短到最短长度 - 记录答案之前,需要判断当前区间是否满足条件,然后再让
i
往前移动
- 枚举每个
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
Java代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int sum = 0, res = Integer.MAX_VALUE;
for(int i = 0, j = 0; i < n; i++){
sum += nums[i];
while(sum - nums[j] >= target){
sum -= nums[j++];
}
if(sum >= target) res = Math.min(res, i - j + 1);
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
有负数的话要怎么处理呢?