Given an array of n positive integers and a positive integer s, find

the minimal length of a contiguous subarray of which the sum ≥ s. If

there isn't one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray

[4,3] has the minimal length under the problem constraint.

解法 BF

思路

暴力解法, 以数组内每一个数为起点, 知道达到s的最小个数.

复杂度

时间O(n^2) 空间O(1)

代码

class Solution {    public int minSubArrayLen(int s, int[] nums) {        int res = 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) {                    res = Math.min(j -i + 1, res);                    break;                }            }        }        return (res == Integer.MAX_VALUE)? 0:res;    }}

解法 双指针

思路

用两个指针来形成一个窗口, 使得窗口的数相加小于s. 如果加和大于s, 则将左边指针右移动, 如果指针小于s, 右边指针左移. 这里要注意的是右边指针可以到达最右边(坐标是数组唱的), 这样才能使左边指针右移找到最优解. 当左右指针相等时候就涵盖了只有一个数的corner case

注意

判定条件是left <= right &&right <= nums.length

复杂度

时间O(n) 空间O(1)

代码

class Solution {    public int minSubArrayLen(int s, int[] nums) {        int left = 0, right = 0, sum = 0, res = Integer.MAX_VALUE;        while (left <=right && right <= nums.length) {            if (sum < s) {                if (right