力扣:209.长度最小的子数组

1.题目分析:

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

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

示例 1:

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

1.找出连续子数组

2.最短长度

3.特殊情况:数组总和小于target,返回零

 2.算法分析:

方法一:暴力枚举:时间复杂度是O(n^3)

设置两个指针,分别表示子数组的开始和子数组的结束两层for循环,最后求子数组总和一个while,自己在脑子想想,跑不过,我就不画图,写代码了哈。

方法二:在暴力枚举的方法上做出改进-->滑动窗口,还是用了双指针,和单调性,全是正数会越加越大,让两个指针同向移动来实现优化

滑动窗口步骤:1.进入窗口

                         2.判断窗口

                         3.退出窗口

 例一图示(target = 7, nums = [2,3,1,2,4,3]):

 

 

 

 

 

 

3.代码编写:

public static int minSubArrayLen(int target, int[] nums) {
        int sum=0;
        int count=Integer.MAX_VALUE;
        int left=0;
        int right=0;
        for(left=0,right=0;right<nums.length;right++)
        {
            sum+=nums[right];//进窗口
            while (sum>=target)//判断
            {
                count=Math.min(count,right-left+1);
                sum-=nums[left++];//出窗口
            }

        }
        if(count==Integer.MAX_VALUE)
        {
            return 0;
        }

        return count;
    }

 

相关推荐

  1. 209-长度数组

    2024-01-18 01:20:03       41 阅读
  2. 面试150题 | 209.长度数组

    2024-01-18 01:20:03       35 阅读
  3. 209. 长度数组(Python3)

    2024-01-18 01:20:03       36 阅读
  4. 209.长度数组

    2024-01-18 01:20:03       10 阅读
  5. 209.长度数组

    2024-01-18 01:20:03       38 阅读
  6. 209. 长度数组

    2024-01-18 01:20:03       49 阅读
  7. 209. 长度数组

    2024-01-18 01:20:03       8 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-01-18 01:20:03       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-01-18 01:20:03       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-01-18 01:20:03       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-01-18 01:20:03       20 阅读

热门阅读

  1. Spring MVC 日期转换器

    2024-01-18 01:20:03       24 阅读
  2. 在 【Linux Centos】下搭建 【Nginx Web】 服务器

    2024-01-18 01:20:03       24 阅读
  3. EXEC sp_addlinkedserver 指定服务器ip

    2024-01-18 01:20:03       29 阅读
  4. 前端导致浏览器奔溃原因分析

    2024-01-18 01:20:03       24 阅读
  5. QT基础篇(7)QT5图形视图框架

    2024-01-18 01:20:03       34 阅读
  6. 力扣909. 蛇梯棋

    2024-01-18 01:20:03       38 阅读
  7. 【学习笔记】[AGC063E] Child to Parent

    2024-01-18 01:20:03       29 阅读
  8. CSS基础

    CSS基础

    2024-01-18 01:20:03      24 阅读