题目

链接

1，暴力求解，

首先最容易想到的是暴力求解，使用两个for循环，一个for循环固定一个数字比如m，另一个for循环从m的下一个元素开始累加，当和大于等于s的时候终止内层循环，顺便记录下最小长度

    public int minSubArrayLen(int s, int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            if (sum >= s)
                return 1;
            for (int j = i + 1; 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;
    }

暴力求解毕竟效率很差，我们来看下其他的解法

2，使用队列相加（实际上我们也可以把它称作是滑动窗口，这里的队列其实就相当于一个窗口）

我们把数组中的元素不停的入队，直到总和大于等于s为止，接着记录下队列中元素的个数，然后再不停的出队，直到队列中元素的和小于s为止（如果不小于s，也要记录下队列中元素的个数，这个个数其实就是不小于s的连续子数组长度，我们要记录最小的即可）。接着再把数组中的元素添加到队列中……重复上面的操作，直到数组中的元素全部使用完为止。
这里以[2,3,1,2,4,3]举例画个图来看下




上面画的是使用队列，但在代码中我们不直接使用队列，我们使用两个指针，一个指向队头一个指向队尾，我们来看下代码

    public int minSubArrayLen(int s, int[] nums) {
        int lo = 0, hi = 0, sum = 0, min = Integer.MAX_VALUE;
        while (hi < nums.length) {
            sum += nums[hi++];
            while (sum >= s) {
                min = Math.min(min, hi - lo);
                sum -= nums[lo++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

看一下运行结果，不过效率还可以，击败了99.85%的用户

3，使用队列相减

第一种是使用相加的方式，这里我们改为相减的方式，基本原理都差不多，

    public int minSubArrayLen(int s, int[] nums) {
        int lo = 0, hi = 0, min = Integer.MAX_VALUE;
        while (hi < nums.length) {
            s -= nums[hi++];
            while (s <= 0) {
                min = Math.min(min, hi - lo);
                s += nums[lo++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

4，二分法查找

我们申请一个临时数组sums，其中sums[i]表示的是原数组nums前i个元素的和，题中说了“给定一个含有 n 个正整数的数组”，既然是正整数，那么相加的和会越来越大，也就是sums数组中的元素是递增的。我们只需要找到sums[k]-sums[j]>=s，那么k-j就是满足的连续子数组，但不一定是最小的，所以我们要继续找，直到找到最小的为止。怎么找呢，我们可以使用两个for循环来枚举，但这又和第一种暴力求解一样了，所以我们可以换种思路，求sums[k]-sums[j]>=s我们可以求sums[j]+s<=sums[k]，那这样就好办了，因为数组sums中的元素是递增的，也就是排序的，我们只需要求出sum[j]+s的值，然后使用二分法查找即可找到这个k。

    public int minSubArrayLen(int s, int[] nums) {
        int length = nums.length;
        int min = Integer.MAX_VALUE;
        int[] sums = new int[length + 1];
        for (int i = 1; i <= length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 0; i <= length; i++) {
            int target = s + sums[i];
            int index = Arrays.binarySearch(sums, target);
            if (index < 0)
                index = ~index;
            if (index <= length) {
                min = Math.min(min, index - i);
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

注意这里的函数int index = Arrays.binarySearch(sums, target);如果找到就会返回值的下标，如果没找到就会返回一个负数，这个负数取反之后就是查找的值应该在数组中的位置
举个例子，比如排序数组[2，5，7，10，15，18，20]如果我们查找18，因为有这个数会返回18的下标5，如果我们查找9，因为没这个数会返回-4（至于这个是怎么得到的，大家可以看下源码，这里不再过多展开讨论），我们对他取反之后就是3，也就是说如果我们在数组中添加一个9，他在数组的下标是3，也就是第4个位置（也可以这么理解，只要取反之后不是数组的长度，那么他就是原数组中第一个比他大的值的下标）

5，直接使用窗口

上面第2种解法我们使用的是使用两个指针，我们也可以把它看做是一个窗口，每次往窗口中添加元素来判断是否满足。其实我们可以逆向思维，先固定一个窗口大小比如leng，然后遍历数组，查看在数组中leng个元素长度的和是否有满足的，如果没有满足的我们就扩大窗口的大小继续查找，如果有满足的我们就记录下窗口的大小leng，因为这个leng不一定是最小的，我们要缩小窗口的大小再继续找……

    public int minSubArrayLen(int s, int[] nums) {
        int lo = 1, hi = nums.length, min = 0;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (windowExist(mid, nums, s)) {
                hi = mid - 1;//找到就缩小窗口的大小
                min = mid;//如果找到就记录下来
            } else
                lo = mid + 1;//没找到就扩大窗口的大小
        }
        return min;
    }

    //size窗口的大小
    private boolean windowExist(int size, int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i >= size)
                sum -= nums[i - size];
            sum += nums[i];
            if (sum >= s)
                return true;
        }
        return false;
    }
size];
            sum += nums[i];
            if (sum >= s)
                return true;
        }
        return false;
    }