lintcode 406. 和大于S的最小子数组

Love The Way You Lie 2023-07-06 14:46 15阅读 0赞

给定一个由 n 个正整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。

样例
    样例 1:
    
    输入: [2,3,1,2,4,3], s = 7
    输出: 2
    解释: 子数组 [4,3] 是该条件下的最小长度子数组。
    样例 2:
    
    输入: [1, 2, 3, 4, 5], s = 100
    输出: -1
    挑战
    如果你已经完成了O(nlogn)时间复杂度的编程，请再试试 O(n)时间复杂度。

class Solution {
        
    public:
        /**
         * @param nums: an array of integers
         * @param s: An integer
         * @return: an integer representing the minimum size of subarray
         */
        int minimumSize(vector<int> &nums, int s) {
        
            // write your code here
            int sum=0;
            int start=0;
            int res=INT_MAX;
            for (int i = 0; i < nums.size(); i++) {
        
                sum+=nums[i];
                while(sum>=s)
                {
         
                    res=min(res,i-start+1);
                    sum-=nums[start];
                    start++;
                }
            }
            return res==INT_MAX?-1:res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心+最小子段和】EDU151 D

[Problem - D - Codeforces][] 题意： ![7a287a1665eb4b0e801397d02468e4a7.png][] ![9449c094

电玩女神/ 2024年03月17日 16:30/ 0 赞/ 59 阅读

相关 lintcode 406. 和大于S的最小子数组

给定一个由 n 个正整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。样例样例 1:

Love The Way You Lie/ 2023年07月06日 14:46/ 0 赞/ 16 阅读

相关 lintcode 32. 最小子串覆盖

给定两个字符串 source 和 target. 求 source 中最短的包含 target 中每一个字符的子串. 样例样例 1: 输入

ゝ一世哀愁。/ 2023年07月03日 08:16/ 0 赞/ 30 阅读

相关 LintCode 41. 最大子数组

（一）题目描述给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。（二）样例样例1: 输入： \[−2,2,−3,4,−1,2,1,−5,3\

红太狼/ 2023年05月30日 10:47/ 0 赞/ 53 阅读

相关非递增顺序的最小子序列[1403]

非递增顺序的最小子序列\[1403\] 题目题解题目给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和严格大于未包含在该

待我称王封你为后i/ 2023年02月26日 04:19/ 0 赞/ 41 阅读

相关具有所有最深结点的最小子树

给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。一个结点的子树是该结点加上它的所

╰半橙微兮°/ 2022年12月08日 15:37/ 0 赞/ 158 阅读

相关 LeetCode1081. 不同字符的最小子序列

题目难度：中等题目描述： > 返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。示例 1： > 输入：s = “bcabc” >

阳光穿透心脏的1/2处/ 2022年10月06日 00:37/ 0 赞/ 184 阅读

相关【lintcode】最大子数组

题目描述：给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。子数组最少包含一个数样例给出数组[−2,2,−3

￡神魔★判官ぃ/ 2022年06月02日 21:08/ 0 赞/ 235 阅读

相关【LintCode 简单】41. 最大子数组

1.问题描述：给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。注意事项子数组最少包含一个数 2.样例：给出数组`[−2,2,−3,

左手的ㄟ右手/ 2022年06月01日 04:07/ 0 赞/ 225 阅读

相关【LintCode 简单】44. 最小子数组

1.问题描述：给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。注意事项子数组最少包含一个数字 2.样例：给出数组\[1, -1,

迈不过友情╰/ 2022年06月01日 04:07/ 0 赞/ 219 阅读