2、题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入: target = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入: target = 4, nums = [1,4,4]
输出: 1
1、思路分析
这道题要找出该数组中满足其和 ≥ target 的长度最小的连续子数组。
直观的方法是枚举数组中每个下标i作为子数组的开始下标,找到满足条件的下标j,然后更新子数组的最小长度也就是j-i+1,但是这种方法实现可能会超出时间限制。
上面说的方法时间复杂度为O(n2),因为找到长度最小的子数组需要O(n)的时间,要全部找一遍需要O(n2)的时间复杂度,那么能不能将时间优化一下呢。
常见的优化方法,可以使用二分查找,就可以将时间复杂度优化到O(log n),使用二分查找,需要创建一个数组用于存储数组的前缀和,前缀和就是从位置1到位置i这个区间内的所有的数字之和,对于每个开始下标i,通过二分查找得到大于或等于i的最小下标,更新子数组的最小长度。
2、代码实现
代码参考:
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
int ans = Integer.MAX_VALUE;
int[] sums = new int[n + 1];
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
for (int i = 1; i <= n; i++) {
int target = s + sums[i - 1];
int bound = Arrays.binarySearch(sums, target);
if (bound < 0) {
bound = -bound - 1;
if (bound <= n) {
ans = Math.min(ans, bound - (i - 1));
return ans == Integer.MAX_VALUE ? 0 : ans;
3、时间复杂度
时间复杂度:O(n log n)
其中n是数组的长度,需要遍历每个下标作为子数组的开始下标,通过二分查找得到长度最小的子数组,二分查找的时间复杂度是O(log n),总时间复杂度为O(n log n)。
空间复杂度:O(n)
其中n是数组的长度。
因为这道题保证了数组中的每个元素都是正值。
那么前缀和一定是递增的,可以保证二分查找是不会出现问题的。
如果数组中不是每个元素都为正的话,就不能使用二分来查找位置了。