Minimum Size Subarray Sum Problem


Description

LeetCode Problem 209.

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [nums_l, nums_l+1, …, nums_r-1, nums_r] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

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

Example 2:

1
2
Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

1
2
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if (nums.size() == 0)
            return 0;
        int minlen = INT_MAX;
        int sum = 0;
        int left = 0;
        for (int i = 0; i < nums.size(); i ++) {
            sum += nums[i];
            while (sum >= s) {
                if (sum - nums[left] >= s) {
                    sum -= nums[left];
                    left ++;
                }
                else {
                    break;
                }
            }
            if (sum >= s)
                minlen = min(minlen, i - left + 1);
        }
        if (minlen == INT_MAX)
            return 0;
        else
            return minlen;
    }
};




Related Posts

1-Bit And 2-Bit Characters Problem

LeetCode 717. We have two special characters, the first character...

Teemo Attacking Problem

LeetCode 495. Our hero Teemo is attacking an enemy Ashe...

Range Addition II Problem

LeetCode 598. You are given an m x n matrix...

Max Consecutive Ones Problem

LeetCode 485. Given a binary array nums, return the maximum...

132 Pattern Problem

LeetCode 456. Given an arrayof n integers nums, a 132...

Summary Ranges Problem

LeetCode 228. You are given a sorted unique integer array...