题目描述

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

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

我的解题思路

双层循环遍历枚举大于target的最小长度的连续子数组

代码

public int minSubArrayLen(int target, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        //看了官方的代码，又优化了一下
        int len = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            if (sum >= target) {
                return 1;
            }
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    //这里模仿了官方的代码，当第一次有符合条件的，len必为j-i+1
                    len = Math.min(len, j - i + 1);
                    break;
                }
            }
        }
        //当len == Integer.MAX_VALUE时，说明这个target大于数组中所有值的和，target不存在
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

时间复杂度&空间复杂度

时间复杂度: O(n2)
空间复杂度: O(1)，这里指的是使用的额外空间

官方解法-前缀和+二分查找

方法一的时间复杂度是 O(n^2)，因为在确定每个子数组的开始下标后，找到长度最小的子数组需要 O(n)O(n) 的时间。如果使用二分查找，则可以将时间优化到 O(\log n)O(logn)。

为了使用二分查找，需要额外创建一个数组sums 用于存储数组nums 的前缀和，其中sums[i] 表示从 nums[0] 到nums[i?1] 的元素和。得到前缀和之后，对于每个开始下标 i，可通过二分查找得到大于或等于 i 的最小下标bound，使得 sums[bound]?sums[i?1]≥s，并更新子数组的最小长度（此时子数组的长度是 bound?(i?1)）。

因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。

这个解法看了好多遍才看懂

看了官方题解写的代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        //sums数组用来存储前缀和
        int[] sums = new int[n + 1];
        //sums[0] = 0表示前0个元素的和为0
        //sums[i]表示前i的元素的和
        sums[0] = 0;
        for (int i = 1; i <= nums.length; i++) {
            //前i个元素的前缀和 = 前i-1个元素的前缀和+nums[i-1]
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int len = Integer.MAX_VALUE;
        int target2;
        for (int i = 1; i <= nums.length; i++) {
            target2 = sums[i - 1] + target;
            //这里使用工具类中的二分查找,这个bound返回的是-(low + 1)
            int bound = Arrays.binarySearch(sums, target2);
            //首先如果这个bound小于0的话，说明数组中不存在等于target2的值，先将其转成正常的边界，由于我们这个题在前缀和大于target2的情况也是满足题意的，
            // 所以最好还是自己写一个二分查找，比较好理解一点，看官方的代码理解了好久
            if (bound < 0) {
                bound = - bound - 1;
            }

            if (bound <= n) {
	            //这里的bound - i + 1就是满足条件的最小子数组的长度，需要理解一下，最好就是自己代一个数组进入debug一下
                len = Math.min(bound - i + 1, len);
            }

        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

时间复杂度

O(Nlog(n)): 一层循环O(N),里面套一个二分查找O(log(N)),所以是O(Nlog(N));

官方解法-滑动窗口

在方法一和方法二中，都是每次确定子数组的开始下标，然后得到长度最小的子数组，因此时间复杂度较高。为了降低时间复杂度，可以使用滑动窗口的方法。

定义两个指针start 和end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和（即从 nums[start] 到 nums[end] 的元素和）。

初始状态下，start 和 end 都指向下标 0，sum 的值为 0。

每一轮迭代，将nums[end] 加到 sum，如果 sum≥s，则更新子数组的最小长度（此时子数组的长度是 end?start+1），然后将 nums[start] 从 sum 中减去并将 start 右移，直到sum<s，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 end 右移。

看了官方题解写的代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        //指针2
        int start = 0;
        //指针1
        int end = 0;
        //保存子数组的最小长度
        int len = Integer.MAX_VALUE;
        //用来维护nums[start]到nums[end]的和
        int sum = 0;
        //循环判断end
        while (end < n) {
            sum += nums[end];
            //sum>target，给len赋值，然后减去nums[start],start右移，寻找最小长度的子数组
            while (sum >= target) {
                len = Math.min(len, end- start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }

        return len == Integer.MAX_VALUE ? 0 : len;
    }
}