Minimum Size Subarray Sum — leetcode[通俗易懂]

Minimum Size Subarray Sum — leetcode

大家好,又见面了,我是全栈君。

题目描写叙述:

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

意思是讲给定一组整数数组nums和一个数字s。求的nums数组中最短长度的连续数字和,使得该和大于等于s。
比方上面实例数组 2 。3。1,2,4,3这一个数组中,大于等于7的最短连续为 3 ,4 那么 minimal为2

解题思路

定义一个start 。表示序列的事实上点,初始值为0
定义一个tempresult,用来累积连续序列和,初始值为0
定义一个minlength,用来表示最短序列。初始值为INT-MAX

  • 一个循环,首先从数组開始处i=0,此时start=0,往后累积和,tempresult+=nums[i]

  • 推断累积和和s的大小,假设大于等于s,则进行例如以下操作

    - 先计算当前minlength=min(minlength,i-satrt+1)
    
    -然后将tempresult的值减去这个序列的nums[start]。起始点start++再次计算minlength(缩短整个序列),然后继续推断该值跟s的大小,直到减去的值使得tempresult的值小于s 
    
  • 假设小于s。则继续累积和。直到满足和大于等于s

  • 注意。还有可能存在不存在序列的,就是整个序列和都相加都小于s。这是就须要推断(程序返回时候i-start==nums.size()&&tempresult小于s

拿上面的数组列子进行解说nums= 2 ,3,1,2,4。3,s=7

首先 从2開始加,一直加到 2,3。1。2此时tempresult=8,大于等于7,先求的但当前minlength=4。然后缩短序列 start++,序列为3。1,2。对应的tempresult=6,小于7。则继续往后面累积和,3,1,2,4,然后缩短序列,变成,1,2,4,start++,此时minlength=3。然后继续缩短,2。4小于7,然后往后面继续累加,2,4,3,大于7,缩短,4,3,大于等于7,minlength=2。,到最后了。结束。

代码例如以下

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {


            int i,start,minlength,tempresult;

    minlength=INT_MAX;
    start=0;
    tempresult=0;
    for(i=start;i<nums.size();i++)
    {
        tempresult+=nums[i];

        if(tempresult>=s)
        {
            minlength=min(minlength,i-start+1);

            tempresult-=nums[start];
            start++;
            while(tempresult>=s)
            {

                minlength=min(minlength,i-start+1);
                tempresult-=nums[start];
                start++;
            }
        }


    }
    if(i-start==nums.size()&&tempresult<s)
        return 0;

    return minlength;
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115496.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 如何用c语言调用c++做成的动态链接库

    今天在做东西的时候遇到一个问题,就是如何在C语言中调用C++做的动态链接库so文件如果你有一个c++做的动态链接库.so文件,而你只有一些相关类的声明,那么你如何用c调用呢,别着急,本文通过一个小小

    2021年12月23日
  • Java实验三_生物总结必修三

    Java实验三_生物总结必修三JAVA第五周作业Java实验报告三第一题实验代码(1)统计该字符串中字母s出现的次数。cpublicclassLetter{publicstaticvoidmain(Str

  • #转载 基于C#通过OPC UA/DA访问PLC学习网站

    #转载 基于C#通过OPC UA/DA访问PLC学习网站#转载#基于C#通过OPCUA/DA访问PLC学习网站今年刚入职的新手,第一次接触OPCUA、OPCDA、C#、PLC,全靠各种百度,经过一个多星期的摸索,基本算是刚入门吧,下面把学习过程中收藏的一些实用的文章和大家分享一下,绝对可以让你少走很多弯路。1.C#读写opcua服务器,浏览所有节点,读写节点,读历史数据,调用方法,订阅,批量订阅操作-dathlin2.C#OPCUA服务器OPCUA网关三菱西门子欧姆龙Modbus转OPCUA服务器可配置的OPCUA服务器网

    2022年10月18日
  • InnoDB数据库隔离级别

    InnoDB数据库隔离级别事务隔离级别分为四种(级别递减):1、Serializable(串行化):最严格的级别,事务串行执行,资源消耗最大;2、REPEATABLEREAD(重复读):保证了一个事务不会修改已经由另一个事务读取但未提交(回滚)的数据。避免了“脏读取”和“不可重复读取”的情况,但不能避免“幻读”,但是带来了更多的性能损失。3、READCOMMITTED(提交读):大多数主流数据库的默认事…

  • JavaScript高级程序设计 第4版(中文高清)扫描版

    JavaScript高级程序设计 第4版(中文高清)扫描版核心ECMAScript文档对象模型DOM浏览器对象模型BOMECMAScript定义语言的基础规定了语言的组成部分:语法、类型、语句、关键字、保留字、操作符、对象

  • 三极管导通条件与电位关系

    三极管导通条件与电位关系npn管导通条件:Ub>Ue,通常e极接地,即Ue为0V。饱和导通是Ub>Ue(锗0.2V/硅0.7V)pnp管导通条件:Ub0V。饱和导通是Ub

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号