- 浏览: 172577 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
在一个数组中,找到一个长度最小的子数组,使它的和大于或等于给定的数字s。我们采用类似滑动窗口的方法来解决。从第一个元素开始,一直累加到和sum大于或等与s,然后我们记录这时的长度。接下来从开始的元素缩小这个窗口,缩小到sum小于s的时候,窗口向右移动,直到移动到数组末尾结束。代码如下:
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.
在一个数组中,找到一个长度最小的子数组,使它的和大于或等于给定的数字s。我们采用类似滑动窗口的方法来解决。从第一个元素开始,一直累加到和sum大于或等与s,然后我们记录这时的长度。接下来从开始的元素缩小这个窗口,缩小到sum小于s的时候,窗口向右移动,直到移动到数组末尾结束。代码如下:
public class Solution { public int minSubArrayLen(int s, int[] nums) { int start = 0; int sum = 0; int minLen = Integer.MAX_VALUE; for(int i = 0; i < nums.length; i++) { sum += nums[i]; if(sum >= s) { while(sum >= s) { minLen = Math.min(minLen, i - start + 1); sum -= nums[start]; start ++; } } } return minLen == Integer.MAX_VALUE ? 0 : minLen; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 223Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 221You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 338Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 329Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 446Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 425Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 424The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 382Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 513Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 526Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 857Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 877Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 549Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 595Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 760Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 728You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 625For a undirected graph with tre ...
相关推荐
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...
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: ...
最大子数组总和maximum subarray sum使用Java语言中的所有复杂度来计算子数组的最大和。 1.O(n ^ 3) 2.O(n ^ 2) 3.O(n)
leetcode 530 Play-with-Algorithms 基本的算法和数据结构 来自liuyubobobo老师的课程 章节 讲解例题 课程练习题 更多扩展练习 ...Subarray Sum 209 3 438 76 713 补充1:更多数组中的问题 [无] [无] 303 121 1
word源码java 玩儿转算法面试 - 课程学习笔记 课程的学习笔记。 课程笔记目录 第一章:算法面试到底是什么鬼 第二章:面试中的复杂度分析 第三章:数组中的问题其实最常见 ...Subarray Sum 3-8 在滑动窗口中做记
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的子数组。如果存在该子数组返回true,否则返回false。 #include #include using namespace std; int main() { std::cout <... subset[i
number of subarray whose sum is S using dynamic programming
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 | ...
LeetCode209_Minimum_Size_Subarray_Sum 给定一个整型数组和一个数字s,找到数组中最短的一个连续子数组, 使得连续子数组的数字和sum>=s,返回这个最短的连续子数组的长度值, 如:给定数组[2,3,1,2,4,3],s=7 答案为...
matlab开发-subarray。从数组中提取子数组。用于功能输出。
最大子序列和问题(Maximum Subarray Sum Problem)是求解一个数组中连续子数组的和的最大值的问题。
最大子数组总和 问题 给定一个整数数组,找到一个具有最大和的序列。 例如,看下面的例子。 let array = [ 1 , - 1 , 5 , 3 , - 7 , 4 , 5 , 6 , - 100 , 4 ] function largestSubarraySum ( array ) { ...
最大子数组总和问题给定一个整数数组,找到一个具有最大和的序列。 看一个例子: let array = [ 1 , - 1 , 5 , 3 , - 7 , 4 , 5 , 6 , - 100 , 4 ]function largestSubarraySum ( array ) { // code to write here}...
python 实现 分治法 (Divide-and-conquer algorithm) 课程设计 ... Max Subarray Sum Mergesort Peak Power 最近的一对点 凸包 堆算法 堆算法迭代 第 K 阶统计 最大差分对 最大子阵列总和 合并排序 峰
Subarray Sum Equals K) Tip3: Knapsack Problem (0/1, unbounded) (#DP 322. Coin Change) Tip4: backtrace or K sum remove duplicates if i != 0 and n == nums[i-1]: (#15. 3Sum) if idx > start and nums[idx] ...
Size K (easy) Smallest Subarray with a given sum (easy) Longest Substring with K Distinct Characters (medium) Fruits into Baskets (medium) No-repeat Substring (hard) Longest Substring with Same Le
Subarray Sum - 无重复字符的最长子串:3. Longest Substring Without Repeating Characters - 最小跳跃步数问题 - 动态规划 + 循环策略优化:45. Jump Game II - 二叉树 前序遍历判断二叉树:98. Validate Binary ...
Subarray Sum Equals K 概括 对于总和问题, 一般有两种方法:一种是二指针技能,另一种是使用Map 对于两个指针技能,它仅在数组排序时有效,以便您知道指针将移动到哪个方向。 对于地图技能,数组可以不排序,您...
easy_Maximum-Subarray 提交链接 / Submit (You need register/login first before submit.) (在提交前你需要先注册或登录) 题目描述 / Description Given an integer array nums, find the contiguous subarray ...
SUBARRAY 应该像第一个例子一样处理所有正常的索引情况(FIND 的输出、范围、未指定的维度)。 唯一的例外是 'end' 关键字,我们必须传入一个字符串并对其进行评估。 我向SUBMAT和SUBMAT_NOEVAL的Garret Euler致敬...