大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个整数数组和正整数target，找出数组中满足≥target的长度最小的子数组，返回其长度。”
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]; // 为了方便计算，令 size = n + 1 // sums[0] = 0 意味着前 0 个元素的前缀和为 0 // sums[1] = A[0] 前 1 个元素的前缀和为 A[0] // 以此类推 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是数组的长度。
三、总结
因为这道题保证了数组中的每个元素都是正值。
那么前缀和一定是递增的，可以保证二分查找是不会出现问题的。
如果数组中不是每个元素都为正的话，就不能使用二分来查找位置了。
