209.minimum-size-subarray-sum.cpp

/*
 * @lc app=leetcode id=209 lang=cpp
 *
 * [209] Minimum Size Subarray Sum
 *
 * https://leetcode.com/problems/minimum-size-subarray-sum/description/
 *
 * algorithms
 * Medium (51.00%)
 * Likes:    14259
 * Dislikes: 535
 * Total Accepted:    1.8M
 * Total Submissions: 3.5M
 * Testcase Example:  '7\n[2,3,1,2,4,3]'
 *
 * Given an array of positive integers nums and a positive integer target,
 * return the minimal length of a subarray whose sum is greater than or equal
 * to target. If there is no such subarray, return 0 instead.
 * 
 * 
 * Example 1:
 * 
 * 
 * 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:
 * 
 * 
 * Input: target = 4, nums = [1,4,4]
 * Output: 1
 * 
 * 
 * Example 3:
 * 
 * 
 * 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^4
 * 
 * 
 * 
 * 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)).
 */

// @lc code=start
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int minLen = 0;
        for (int i = 0, j = 0; i < nums.size(); ++i) {
            if (nums[i] == target) {
                return 1;
            }
            sum += nums[i];
            while (sum >= target && j < i) {
                if (sum - nums[j] < target) {
                    break;
                }
                sum -= nums[j++];
            }
            if (sum >= target) {
                //cout << j << ',' << i << endl;
                int len = i - j + 1;
                if (minLen == 0 || minLen > len) {
                    minLen = len;
                }
            }
        }
        return minLen;
    }
};
// @lc code=end

// test cases:
// 11\n[1,2,3,4,5]
// 7\n[2,3,1,2,4,3]