`

Minimum Size Subarray Sum

阅读更多
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的时候,窗口向右移动,直到移动到数组末尾结束。代码如下:
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;
    }
}
0
2
分享到:
评论

相关推荐

    python-leetcode面试题解之第76题最小覆盖子串-题解.zip

    这个话题是LeetCode上的第76题——"最小覆盖子串"(Minimum Size Subarray Sum)。LeetCode是一个广受欢迎的在线平台,它提供了各种编程挑战,帮助开发者提升技能,准备技术面试。这道题目主要涉及字符串处理和动态...

    leetcode常见的100热点算法题

    8. **栈与队列**:"Valid Parentheses"(有效括号)和"Minimum Size Subarray Sum"(最小覆盖子数组)这类题目会用到栈和队列的特性来处理问题。 9. **位操作**:位操作是计算机科学的基础,题目如"Number of 1 ...

    Coding Interview in Java

    6. 动态规划问题:如Minimum Size Subarray Sum(最小大小的子数组和),这通常需要使用动态规划方法来找到最优解。 7. 双指针技术:常用于处理有序数组或排序后的数据结构,如在Two Sum II、Remove Duplicates ...

    leetcode530-alogritme-interview:alogritme-面试

    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...

    leetcode分类-leetcode:leetcode

    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: ...

    leetcode530-Play-with-Algorithms:基本的算法和数据结构

    leetcode 530 Play-with-Algorithms 基本的算法和数据结构 来自liuyubobobo老师的课程 章节 讲解例题 课程练习题 更多扩展练习 ...Subarray Sum 209 3 438 76 713 补充1:更多数组中的问题 [无] [无] 303 121 1

    word源码java-Play-with-Algorithm-Interview-Learningnotes:Play-with-Algori

    word源码java 玩儿转算法面试 - 课程学习笔记 课程的学习笔记。 课程笔记目录 第一章:算法面试到底是什么鬼 第二章:面试中的复杂度分析 第三章:数组中的问题其实最常见 ...Subarray Sum 3-8 在滑动窗口中做记

    LeetCode最全代码

    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-LeetCode209_Minimum_Size_Subarray_Sum:给定一个整型数组和一个数字s,找到数组中最

    LeetCode209_Minimum_Size_Subarray_Sum 给定一个整型数组和一个数字s,找到数组中最短的一个连续子数组, 使得连续子数组的数字和sum&gt;=s,返回这个最短的连续子数组的长度值, 如:给定数组[2,3,1,2,4,3],s=7 答案为...

    leetcode:LeetCode练习

    7. **堆和队列**:如“最小覆盖子集”(Minimum Size Subarray Sum),需要找到使数组元素和大于等于给定目标的最小子数组长度。 每个问题的解决方案通常会展示出不同的编程技巧和算法思想,如分治法、贪心策略、递归...

    leetcode209-LeetCode209_MinSizeSubarraySum:LeetCode209_MinSizeSubarrayS

    标题 "LeetCode209-LeetCode209_MinSizeSubarraySum:LeetCode209_MinSizeSubarrayS" 指向的是LeetCode上的第209题,该题目名为"Minimum Size Subarray Sum"(最小连续子数组和)。这是一道与数组处理和动态规划相关...

    LeetCode

    6. **堆数据结构**:JavaScript 中可以使用数组模拟堆,如“最小堆”(Minimum Size Subarray Sum)问题,需要你找到使数组元素和大于等于给定值的最小子数组长度。 7. **图和树**:虽然 JavaScript 不像 C++ 或 ...

    LeetCode-Feb2021

    滑动窗口则在处理数组/字符串的连续子序列问题时有用,如"Minimum Size Subarray Sum"(最小覆盖子数组的和)。 十、图的遍历与最短路径 Java中的图通常用邻接矩阵或邻接表表示,如"Course Schedule"(课程表)。...

    算法学习指南.docx

    - **样题参考**:`minimum-size-subarray-sum`要求找到和大于等于特定值的最小子数组长度。 在准备算法面试或提升编程技能时,应重点关注这些高频考点,通过实践样题并理解官方解法和解题套路,可以有效地提高解决...

Global site tag (gtag.js) - Google Analytics