LeetCode 209.

Question

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.

Intuition

On first try, I use BS to locate the answer. The time complexity is O(nlogn)

After that, I saw the sliding window tag and then I tried use it on this problem.

Complexity

Time complexity: O(nlogn)
Space complexity: O(n)

Code (BS)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = nums.length;
        while (left <= right) {// logn
            int mid = left + (right - left) / 2;
            int result = 0;
            for (int i=0; i<mid; i++) {
                result += nums[i];
            }
            if (result >= target) {
                right = mid - 1;
                continue;
            }
            for (int i=mid; i<nums.length; i++) { //n
                result -= nums[i-mid];
                result += nums[i];
                if (result >= target) {
                    break;
                }
            }
            if (result >= target) {
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left > nums.length ? 0 : left;
    }
}

Complexity

Time complexity: O(n)
Space complexity: O(n)

Code (Sliding Window)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, r = 0;
        int sum = 0, ans = 100001;

        while (r < nums.length) {
            sum += nums[r];
            while (sum >= target) {
                ans = Math.min(ans, r - l + 1);
                sum -= nums[l];
                l++;
            }
            r++;
        }
        return ans > nums.length ? 0 : ans;
    }
}

Check out the description of this problem at LC 209.