☆打卡算法☆LeetCode 209. 长度最小的子数组 算法解析
☆打卡算法☆LeetCode 209. 长度最小的子数组 算法解析
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个整数数组和正整数target，找出数组中满足≥target的长度最小的子数组，返回其长度。”
题目链接：
来源：力扣（LeetCode）
链接： 209. 长度最小的子数组 - 力扣（LeetCode）
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是数组的长度。
三、总结
因为这道题保证了数组中的每个元素都是正值。
那么前缀和一定是递增的，可以保证二分查找是不会出现问题的。
如果数组中不是每个元素都为正的话，就不能使用二分来查找位置了。