解题报告 - 209. 长度最小的子数组

LeetCode 209. 长度最小的子数组

@TOC

题目描述

 给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

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

一、解题关键词

连续子数组
>= taeget
最小
返回长度

二、解题报告

1.思路分析

1. 肯定需要一个循环进行累加且求最值
2. Math 一定需要
3. 数组无序
4. 需要计算长度 right - left ，两个坐标都需要移动 所以需要两个循环

2.时间复杂度

3.代码示例

解答一：前綴和

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int ans = Integer.MAX_VALUE;
        int[] sum = new int[len + 1];

        for(int i = 1; i<= len; i++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        for(int i = 1; i <= len; i++){
            int s = target + sum[i - 1];
            int bound = Arrays.binarySearch(sum,s);
            if(bound < 0){
                bound = -bound - 1;
            }
            if(bound <= len){
                ans = Math.min(ans,bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

解答二：滑动窗口(效率更高)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int res = Integer.MAX_VALUE;
        int left = 0,right = 0;
        int sum = 0;
        
        while(right < len){
            sum += nums[right];
            while(sum >= target){
                res = Math.min(res,right - left + 1);
                sum -= nums[left];
                left ++;
            }
            right ++;
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

4.知识点

时间复杂度
    1、二分 logn
    2、滑动窗口 n