[数据结构与算法]【蓝桥Java每日一题】——10.长度最小的子数组

??引言??

? ? ? ? ? ? ? ?大家好啊，我是执梗。今天带来一道非常好的题目——长度最小的子数组。为什么好呢？因为它O(nlogn)时间复杂度的解法比O(n)更加难想到，而题目的进阶做法却又恰恰需要我们使用O(nlogn)的复杂度去做。

??精彩回放??

🍇长度最小的子数组

给定一个含有?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;
    }
}

????????看完如果让你有一丝收获，球球感谢给一个三连支持！！！

? ? ? ? ? ? ? ??