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.
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.
Challenge
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
int minimumSize(vector<int> &nums, int s) { int n = nums.size(); int minLen = n+1; int sum = 0; int left = 0; for(int i=0; i<n; i++) { sum += nums[i]; while(sum >= s) { int len = i-left+1; minLen = min(minLen, len); sum -= nums[left++]; } } return minLen>n ? 0 : minLen; }
相关推荐
子阵列划分的root-music algorithm
最大子数组总和问题给定一个整数数组,找到一个具有最大和的序列。 看一个例子: let array = [ 1 , - 1 , 5 , 3 , - 7 , 4 , 5 , 6 , - 100 , 4 ]function largestSubarraySum ( array ) { // code to write here}...
最大子数组总和maximum subarray sum使用Java语言中的所有复杂度来计算子数组的最大和。 1.O(n ^ 3) 2.O(n ^ 2) 3.O(n)
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的子数组。如果存在该子数组返回true,否则返回false。 #include #include using namespace std; int main() { std::cout <... subset[i
希望更多的人能和我一样,把本狂想曲系列中的任何一道面试题当做一道简单的编程题或一个实质性的问题来看待,在阅读本狂想曲系列的过程中,希望你能尽量暂时放下所有有关面试的一切包袱,潜心攻克每一道“编程题”,...
matlab开发-subarray。从数组中提取子数组。用于功能输出。
number of subarray whose sum is S using dynamic programming
leetcode 2 code_interview leetcode和lintcode的一些题目的解法 是剑指offer 是面试中遇到的有意思的题目总结,...138-Subarray-Sum integer-arr 整型数组 值得回顾的题 41-first-missing-positive 01-Two-Sum 求解第K
最大子数组总和 问题 给定一个整数数组,找到一个具有最大和的序列。 例如,看下面的例子。 let array = [ 1 , - 1 , 5 , 3 , - 7 , 4 , 5 , 6 , - 100 , 4 ] function largestSubarraySum ( array ) { ...
LeetCode209_Minimum_Size_Subarray_Sum 给定一个整型数组和一个数字s,找到数组中最短的一个连续子数组, 使得连续子数组的数字和sum>=s,返回这个最短的连续子数组的长度值, 如:给定数组[2,3,1,2,4,3],s=7 答案为...
Minimum Size Subarray Sum 209 3 438 76 第二章 查找表相关问题 2-1 set的使用 Intersection of Two Arrays 349 2-2 map的使用 Intersection of Two Arrays II 350 2-3 set和map不同底层实现的区别 349 350 136 242...
lru cache leetcode leetcode 记录自己刷leetcode时...subarray-sum-equals-k binary-tree-preorder-traversal n-queens-ii populating-next-right-pointers-in-each-node sum-root-to-leaf-numbers best-time-to-buy
easy_Maximum-Subarray 提交链接 / Submit (You need register/login first before submit.) (在提交前你需要先注册或登录) 题目描述 / Description Given an integer array nums, find the contiguous subarray ...
leetcode 530 Play-with-Algorithms 基本的算法和数据结构 来自liuyubobobo老师的课程 章节 讲解例题 课程练习题 更多扩展练习 ...Subarray Sum 209 3 438 76 713 补充1:更多数组中的问题 [无] [无] 303 121 1
word源码java 玩儿转算法面试 - 课程学习笔记 课程的学习笔记。 课程笔记目录 第一章:算法面试到底是什么鬼 第二章:面试中的复杂度分析 第三章:数组中的问题其实最常见 ...Subarray Sum 3-8 在滑动窗口中做记
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
Subarray Sum 滑动窗口需要记录 Leetcode Java Python Leetcode.3 Longest Substring Without Repeating Characters Leetcode.76 Minimum Window Substring Leetcode.438 Find All Anagrams in a String Pattern: ...
import SubarrayProxy from 'ember-subarray-proxy' ; var slice = SubarrayProxy . create ( { content : Ember . A ( [ 'a' , 'b' , 'c' ] ) , limit : 2 } ) ; slice . get ( 'length' ) // 2 slice . get ( '...
npm install max-subarray bower install max-subarray 用法 const maxSubarray = require ( 'max-subarray' ) ; console . log ( maxSubarray ( [ 1 , - 4 , 1 , 3 , 6 , - 2 , - 9 ] ) ) ; // [1, 3, 6] console ....
最大子序列和问题(Maximum Subarray Sum Problem)是求解一个数组中连续子数组的和的最大值的问题。