LeetCode 长度最小的子数组

题目：

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

思路：

非常明显用滑动窗口处理

时间复杂度O（n）

代码：

public int minSubArrayLen(int s, int[] nums) {

        int n = nums.length;

        if(n == 0){

            return 0;

        }

        int lo = 0;

        int hi = 0;

        int sum = 0;

        int res = Integer.MAX_VALUE;

        for(int i = 0;i<n;i++){

            sum += nums[i];

            hi++;

            if(sum>=s){

                res = res<=hi-lo?res:hi-lo;

                while(sum>=s){

                    res = res<=hi-lo?res:hi-lo;

                    sum -= nums[lo++];

                }

            }

        }

        return res+1<0?0:res;

    }

法二：前缀数组+二分查找

法三：双指针（道理同法一）

巴特西

LeetCode 长度最小的子数组

最新文章

热门文章