[滑动窗口 二分查找] 209. 长度最小的子数组（暴力解 → 滑动窗口法 → 二分查找法）

[滑动窗口 二分查找] 209. 长度最小的子数组（暴力解 → 滑动窗口法 → 二分查找法）

• • 209. 长度最小的子数组

209. 长度最小的子数组

题目链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

---

分类：

• 数组（无序数组）
• 滑动窗口（思路2：O(N) 寻找连续子数组）
• 二分查找（思路3：用 无序数组nums 构造 有序数组sums、问题转化：求nums的最小连续子数组长度 → 在sums上二分查找 >= sums[i] + s的最小值）

---

思路1：暴力解（O(N^2)）

维护一个min在算法过程中不断迭代更新，保存当前满足题目要求的最小连续子数组长度。

依次枚举数组的元素，对于第i个元素，寻找以该节点为起点的连续子数组和>=s的最小长度，然后更新min，i++。（i=0~n-1）

• 注意：特殊用例的处理，min初始值设置为Integer.MAX_VALUE，但如果找不到符合条件的子数组不能返回min初始值，而需要返回0，所以在返回前要先做一个判断，如果min等于初始值，说明没有找到解，返回0。

实现代码：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++){
            int sum = 0;
            for(int j = i; j < nums.length; j++){
                sum += nums[j];
                if(sum >= s){
                    min = Math.min(min, j - i + 1);
                    break;
                }
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

• 时间复杂度：O(N^2)

思路2：滑动窗口法（O(N)，推荐）

算法流程

设置两个指针分别作为滑动窗口的左右边界left,right。初始值left=0,right=0，设置一个变量sum表示滑动窗口内的元素之和，初始值sum=nums[0]。

滑动窗口开始工作：

• 如果窗口内元素之和sum < s，则r++，sum+=nums[r]；

• 如果窗口内元素之和sum > s，则先更新min，再做sum-=nums[l]，l++；

• 如果窗口内元素之和sum == s，则先更新min，sum-=nums[l],l++ and r++, sum+=nums[r]，即左右边界同时移动一位。（因为sum == s时，如果只移动左边界则sum必定<s，如果只移动右边界则sum必定>s，所以两个边界都移动更高效）

  • 注意：r++后取nums[right]之前要记得做越界判断。

窗口边界发生变化后，再回到算法开头重新执行，直到：

• r == n-1 && sum <= s ：表示右边界已经到达最后一个元素，但窗口内元素之和仍小于s，则不可能再得到>=s的情况。
• 或 r-l == 0 && sum == s ：表示窗口内只有一个元素，且元素之和==s，说明已经得到最小子数组长度，不必再往下找了。

实现代码：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        //特殊用例如：nums=[]，直接返回0
        if(nums == null || nums.length == 0) return 0;
        
        int min = Integer.MAX_VALUE;
        int left = 0, right = 0;//滑动窗口的左右边界
        int sum = nums[0];//滑动窗口内的元素之和
        while(right < nums.length){
            //如果元素之和<s，则扩大右边界一位right++
            if(sum < s){
                right++;
                //取nums[right]之前记得判断越界
                if(right < nums.length) sum += nums[right];
            }
            //如果元素之和>s，说明当前窗口满足题目要求，记录窗口大小，然后缩小左边界left++
            else if(sum > s){
                min = Math.min(min, right - left + 1);
                sum -= nums[left];//注意先减去最左端元素，再做left--
                left++;
            }
            //如果元素之和==s,说明当前窗口满足题目要求，记录窗口大小，然后可以同时移动左右边界
            else if(sum == s){
                min = Math.min(min, right - left + 1);
                if(min == 1) break;//如果已经找到最小长度1，则直接退出当前流程
                //同步移动左右边界
                sum -= nums[left];
                left++;
                right++;
                //取nums[right]之前记得判断越界
                if(right < nums.length) sum += nums[right];
            }
        }
        //如果不存在符合条件的子数组，则min仍为初始值，返回 0；有解则返回最小长度
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

• 时间复杂度：算法每执行一次，都至少有一个窗口边界发生移动，这样在最差情况下例如：[1,1,1,1,1,6] s = 7，则需要不断做r++，直到r=5,sum=11>s才能得到一个解，但还不是最优解，需要不断做l++，直到l=4，sum=7==s，才能得到最优解，所以l,r合起来一共移动了2n次，所以时间复杂度为O(N)。

思路3：二分查找 （NlogN，思路转变）

题目提示使用O(NlogN)来解题，可以想到O(logN)可以使用二分查找，但二分查找是基于有序数组，所以我们需要先构造一个有序数组。

设置一个数组sums，sums[i]表示nums前i个元素之和，因为nums的元素都是正数，所以sums的元素都是递增的，sums数组就是一个有序数组，可以在上面做二分查找。

因为sums[0]表示nums前0个元素之和，即sums[0]表示0个元素之和，所以sums[0]=0，sums[1]=sums[0]+nums[0]，sums[2]=sums[1]+nums[1]，以此类推，得到：

sums[i] = sums[i-1] + nums[i-1]（i>0）
        = 0 (i == 0)

也就是说sums需要设置一个sums[0]保存0个元素之和的情况，所以sums数组的大小为nums.length+1.

在sums上有：

sums[2]-sums[0]=nums[1]+nums[0],
sums[2]-sums[1]=nums[1]+nums[0]-nums[0]=nums[1]

则sums[j] - sums[i] = nums[i~j-1]之和（i=0~n-1，j = 1~n就可以表示nums上的所有子数组），j - i 就是sums[j] - sums[i]所包含的nums元素个数。

我们要找的是元素之和>=s的子数组，所以相当于要在sums上找到i,j使得sums[j]-sums[i] >= s，不等式可以转换为sums[i] + s <= sums[j]，问题也相应转化为枚举sums[i]，然后在sums上二分查找 >=sums[i]+s的最小值的位置 j，最后计算 j - i 即为一个满足条件的子数组的长度。

二分查找就按常规的二分查找迭代实现即可：

• 如果sums中存在 == sums[i]+s的元素，则返回该元素的下标；
• 如果不存在刚好==sums[i]+s的元素，则在退出二分查找时left>right，返回left，就是此时指向>=sums[i]+s的最小值的下标。

实现代码：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        //特殊用例如：nums=[]，直接返回0
        if(nums == null || nums.length == 0) return 0;
        
        int min = Integer.MAX_VALUE;

        //构造sums数组+初始化
        int[] sums = new int[nums.length + 1];
        for(int i = 1; i < sums.length; i++){
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        //在sums上枚举i
        for(int i = 0; i < nums.length; i++){
            int target = sums[i] + s;//待查找目标
            //调用二分查找函数在整个sums中查找>=target的最小值的下标
            int index = binarySearch(sums, target);
            //下标>=0说明找到target,更新min
            if(index >= 0){
                min = Math.min(min, index - i);
            }
        }

        //如果不存在符合条件的子数组，则min仍为初始值，返回 0；有解则返回最小长度
        return min == Integer.MAX_VALUE ? 0 : min;
    }
    //二分查找迭代实现：查找>=target的最小值（常规的二分实现就能满足）
    //1,2,3,4,6,7,8
    //target=5 
    public int binarySearch(int[] sums, int target){
        int left = 0, right = sums.length - 1;//查找区间为左右闭区间[left,right]
        //如果不存在>=target的元素，说明每个sums元素都<target，则返回-1,表示未能找到>=target的元素
        if(sums[right] < target) return -1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(sums[mid] == target) return mid;
            else if(sums[mid] < target) left = mid + 1;
            else if(sums[mid] > target) right = mid - 1;
        }
        return left;//返回的是>=target的元素下标
    }
}

• 时间复杂度：在sums上枚举i，需要O(N)，然后二分查找sums[i]+s的位置，需要O(logN)，整理得O(NlogN).