⭐️引言⭐️
大家好啊，我是执梗。今天带来一道非常好的题目——长度最小的子数组。为什么好呢？因为它O(nlogn)时间复杂度的解法比O(n)更加难想到，而题目的进阶做法却又恰恰需要我们使用O(nlogn)的复杂度去做。
⭐️精彩回放⭐️
2022.1.18——Java每日一练【蓝桥Java每日一练】——9.回文链表2022.1.16——Java每日一练【蓝桥Java每日一练】——8.计算力扣银行的钱2022.1.14——Java每日一练【蓝桥Java每日一练】——7.至少是其他数字两倍的最大数2022.1.11——Java每日一练【蓝桥Java每日一练】————6.二叉树的前中后序遍历（递归与迭代）2022.1.9——Java每日一练【蓝桥Java每日一练】————5.按键持续时间最长的键
🍇长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的** 连续子数组 **[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
题目链接：长度最小的子数组
题目的要求很简单，就是找出相加之和大于等于target且长度最短的子数组，这道题目之所以很好，因为它的解法很多，在这我只写出它最经典的三种写法。大家看到这道题能想到多少种解法呢？
🍇** 1.暴力循环**
** 时间复杂度O(n^2)：两层for循环**
** 空间复杂度O(1)**
** **首先最容易想到的方法肯定是暴力遍历，无论什么题我们都可以先去思考暴力能否AC。我们可以通过第一层循环定下一个数组a，a为某个子数组的起始下标。内层循环我们从a往后累加，找到恰好相加和>=s的下标b，记录下此时的最小长度min，然后循环中每次更新min。当然min的初始值为Integer.MAX_VALUE，如果循环以后min没变说明数组没有合适的子数组，返回0即可。
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
if (sum >= s) {
ans = Math.min(ans, j - i + 1);
break;
}
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
🍇**2.前缀和+二分**
** 时间复杂度O(nlogn)：**其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是O(n)，对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 O(logn)，因此总时间复杂度是O(nlogn)。
**空间复杂度O(n)**：主要是前缀和数组的开销
** 其实如果对前缀和足够熟练，当看到这种求连续子数组的问题时就要去思考前缀和的可行性，这道题是可以的，且可以搭配二分，只是代码比较复杂，较容易出错。我们首先用一个数组arr去保存原数组nums的前缀和，arr[i]的意思为nums数组中前i个元素的和。**首先我们要清楚如何去使用前缀和数组，既然要找到一个连续子数组大于等于target，那就是需要去找到两个下标i和k满足这个公式。当然我们不可能两层for循环去找满足的k和j下标，我们可以转化为
（有点类似力扣第一题两数之和的思想）。然后遍历arr数组，通过二分查找去找k。
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n=nums.length;
int[] arr=new int[n+1];
//填充前缀和数组
for(int i=1;i<=n;i++){
arr[i]=arr[i-1]+nums[i-1];
}
int min=Integer.MAX_VALUE;
for(int i=0;i<=n;i++){
int target=s+arr[i];
int index=Arrays.binarySearch(arr,target);
if(index<0){
index=~index;
}
if(index<arr.length){
min=Math.min(min,index-i);
}
}
return min==Integer.MAX_VALUE?0:min;
}
}
**代码问题讲解：**
** **首先这里的二分我使用的是Arrays.binarySearch这个Java自带的二分方法，因为这里如果再手写二分不仅容易错而且代码会显得非常长（其实就是怕错-。-）。当然我们得会使用这个方法。首先使用这个方法传入的数组必须是有序的（二分查找的要求），如果它找到的话就会返回下标，否则会返回一个负数，如果这时我们对这个返回的index取反，就可以得到待查找的数在这个数组中应该插入的位置。
举个例子，比如排序数组 [2，5，7，10，15，18，20] 如果我们查找 15，因为有这个数会返回 15的下标 4，如果我们查找 9，因为没这个数会返回 -4（至于这个是怎么得到的，大家可以看下源码，这里不再过多展开讨论），我们对他取反之后就是3，也就是说如果我们在数组中添加一个 9，他在数组的下标是 3，也就是第 4 个位置（也可以这么理解，只要取反之后不是数组的长度，那么他就是原数组中第一个比他大的值的下标）
🍇**3.滑动窗口**
** 时间复杂度O(n)：**n是数组的长度，其中i和j最多各移动n次
** 空间复杂度O(1)**
** ** 滑动窗口绝对是解决这道题非常优秀的办法，它的思路简单，代码量少而且复杂度只需要O(n)且不需要额外的空间。
定义两个指针i和j分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和（即从 num[i]到nums[j] 的元素和）。初始状态下，i和j都指向下标0吗，sum初始为0。 每一轮迭代，将nums[j]加到sum，如果sum>=s，则更新子数组的最小长度（此时子数组的长度是j-i+1），然后将 nums[i] 从 sum中减去并将 i 右移，直到 sum<s，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将j 右移。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
//记录答案最长
int result=Integer.MAX_VALUE;
//滑动窗口的起始位置，左边界
int i=0;
//记录窗口内的总和
int sum=0;
// 滑动窗口的长度
int subLength = 0;
//j作为滑动窗口的右边界
for(int j=0;j<nums.length;++j){
sum=sum+nums[j];
while(sum>=target){
subLength=j-i+1;
result=Math.min(subLength,result);
sum-=nums[i++];
}
}
return result==Integer.MAX_VALUE?0:result;
}
}
**看完如果让你有一丝收获，球球感谢给一个三连支持！！！**
版权归原作者 执 梗 所有， 如有侵权，请联系我们删除。