【Leetcode】209. Minimum Size Subarray Sum（求子区间）

矫情吗；* 2022-01-28 00:29 164阅读 0赞

Given an array of **n** positive integers and a positive integer **s**, find the minimal length of a **contiguous** subarray of which the sum ≥ **s**. If there isn't one, return 0 instead.

**Example:**

Input: s = 7, nums = [2,3,1,2,4,3]
    Output: 2
    Explanation: the subarray [4,3] has the minimal length under the problem constraint.

**Follow up:**

If you have figured out the *O*(*n*) solution, try coding another solution of which the time complexity is *O*(*n* log *n*).

题目大意：

题目中给出一个目标，和一个数组，求出长度最少的区间满足和>=s。

解题思路：

从第一个位置开始遍历，当找到满足要求时将左标签l向右移动。保存最小距离，再将右标签r向右移动。

class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            // O(n) l and r
            int n = nums.size();
            int ans = INT_MAX;
            int l = 0, r = 0;
            int sum = 0;
            while(r<n){
                sum += nums[r];
                while(sum>=s){
                    ans = min(ans, r+1-l);
                    sum -= nums[l++];
                }
                r++;
            }
            return (ans==INT_MAX)?0:ans;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode 209. Minimum Size Subarray Sum | 209. 长度最小的子数组（Java）

题目 [https://leetcode.com/problems/minimum-size-subarray-sum/][https_leetcode.com_prob

心已赠人/ 2022年10月06日 04:50/ 0 赞/ 152 阅读

相关 Leetcode 523. Continuous Subarray Sum

有趣的dp 我们要求的是num\[L\] + num\[L+1\] + … + num\[R\] mod k 是否等于零。所以我求一个前缀和A\[L\] + A\[L+1

深碍√TFBOYSˉ_/ 2022年09月27日 00:26/ 0 赞/ 142 阅读

相关 Minimum Size Subarray Sum（C++长度最小的子数组）

（1）双指针 class Solution { public: int minSubArrayLen(int target, vecto

雨点打透心脏的1/2处/ 2022年09月02日 01:12/ 0 赞/ 125 阅读

相关 leetcode 907. Sum of Subarray Minimums | 907. 子数组的最小值之和（单调栈）

题目 [https://leetcode.com/problems/sum-of-subarray-minimums/][https_leetcode.com_probl

男娘i/ 2022年08月28日 06:54/ 0 赞/ 3 阅读

相关 leetcode 209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length

电玩女神/ 2022年08月20日 15:15/ 0 赞/ 161 阅读

相关 [leetcode]209. Minimum Size Subarray Sum -- JavaScript 代码

/ @param {number} s @param {number[]} nums @return {number} / var minSubArray

清疚/ 2022年07月17日 03:12/ 0 赞/ 50 阅读

相关 leetcode 209. Minimum Size Subarray Sum 最短子数组的和 + 十分典型的移动窗口做法

Given an array of n positive integers and a positive integer s, find the minimal length

àì夳堔傛蜴生んèń/ 2022年06月08日 09:16/ 0 赞/ 174 阅读

相关【Leetcode】209. Minimum Size Subarray Sum（求子区间）

Given an array of n positive integers and a positive integer s, find the minimal length

矫情吗；*/ 2022年01月28日 00:29/ 0 赞/ 165 阅读

相关 209. Minimum Size Subarray Sum

class Solution { public int minSubArrayLen(int s, int[] nums) {

待我称王封你为后i/ 2021年12月22日 06:57/ 0 赞/ 136 阅读

相关 [Leetcode] Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

超、凢脫俗/ 2021年12月03日 07:19/ 0 赞/ 185 阅读