- 浏览: 183720 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 265Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 267You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 384Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 374Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 500Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 563Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 475Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 664Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 469The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 430Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 575Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 581Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 426All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 898Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 930Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 602Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 676Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 845Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 783You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 707For a undirected graph with tre ...
相关推荐
这个话题是LeetCode上的第76题——"最小覆盖子串"(Minimum Size Subarray Sum)。LeetCode是一个广受欢迎的在线平台,它提供了各种编程挑战,帮助开发者提升技能,准备技术面试。这道题目主要涉及字符串处理和动态...
8. **栈与队列**:"Valid Parentheses"(有效括号)和"Minimum Size Subarray Sum"(最小覆盖子数组)这类题目会用到栈和队列的特性来处理问题。 9. **位操作**:位操作是计算机科学的基础,题目如"Number of 1 ...
6. 动态规划问题:如Minimum Size Subarray Sum(最小大小的子数组和),这通常需要使用动态规划方法来找到最优解。 7. 双指针技术:常用于处理有序数组或排序后的数据结构,如在Two Sum II、Remove Duplicates ...
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: ...
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 | ...
LeetCode209_Minimum_Size_Subarray_Sum 给定一个整型数组和一个数字s,找到数组中最短的一个连续子数组, 使得连续子数组的数字和sum>=s,返回这个最短的连续子数组的长度值, 如:给定数组[2,3,1,2,4,3],s=7 答案为...
7. **堆和队列**:如“最小覆盖子集”(Minimum Size Subarray Sum),需要找到使数组元素和大于等于给定目标的最小子数组长度。 每个问题的解决方案通常会展示出不同的编程技巧和算法思想,如分治法、贪心策略、递归...
标题 "LeetCode209-LeetCode209_MinSizeSubarraySum:LeetCode209_MinSizeSubarrayS" 指向的是LeetCode上的第209题,该题目名为"Minimum Size Subarray Sum"(最小连续子数组和)。这是一道与数组处理和动态规划相关...
6. **堆数据结构**:JavaScript 中可以使用数组模拟堆,如“最小堆”(Minimum Size Subarray Sum)问题,需要你找到使数组元素和大于等于给定值的最小子数组长度。 7. **图和树**:虽然 JavaScript 不像 C++ 或 ...
滑动窗口则在处理数组/字符串的连续子序列问题时有用,如"Minimum Size Subarray Sum"(最小覆盖子数组的和)。 十、图的遍历与最短路径 Java中的图通常用邻接矩阵或邻接表表示,如"Course Schedule"(课程表)。...
- **样题参考**:`minimum-size-subarray-sum`要求找到和大于等于特定值的最小子数组长度。 在准备算法面试或提升编程技能时,应重点关注这些高频考点,通过实践样题并理解官方解法和解题套路,可以有效地提高解决...