Question

Formatted question description: https://leetcode.ca/all/209.html

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⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

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

Algorithm

Note that this is greater than or equal to, not equal to.

Define two pointers left and right to record the left and right boundary positions of the sub-array respectively, and then move right to the right,

Until the sub-array sum is greater than or equal to the target value
Or right reaches the end of the array, At this point, update the shortest distance, and move the left image to the right by one, and then subtract the removed value from the sum, and then repeat the above steps until right reaches the end and left reaches the critical position (that is, either reaches the boundary or again move to the right), and the sum will be checked.

Code

public class Minimum_Size_Subarray_Sum {

    // time: O(N)
    // space: O(1)
    class Solution {
        public int minSubArrayLen(int s, int[] nums) {

            int i = 0; // left pointer
            int j = 0; // right pointer

            int minLength = Integer.MAX_VALUE;
            int sum = 0;
            for (; j < nums.length; j++) {
                sum += nums[j];

                while (sum >= s) {

                    minLength = Math.min(minLength, j - i + 1);

                    sum -= nums[i];
                    i++;
                }
            }

            return minLength == Integer.MAX_VALUE ? 0 : minLength;
        }
    }

    // time: O(NlogN)
    // space: O(N)
    class Solution_binarySearch {
        public int minSubArrayLen(int s, int[] nums) {
            int len = nums.length;
            int[] sums = new int[len + 1];
            int res = len + 1;

            for (int i = 1; i < len + 1; ++i) {
                sums[i] = sums[i - 1] + nums[i - 1];
            }

            // binary search
            for (int i = 0; i < len + 1; ++i) {
                int right = searchRight(i + 1, len, sums[i] + s, sums);
                if (right == len + 1) break;
                if (res > right - i) res = right - i;
            }

            return res == len + 1 ? 0 : res;
        }
        int searchRight(int left, int right, int key, int sums[]) {
            while (left <= right) {
                int mid = (left + right) / 2;
                if (sums[mid] >= key) right = mid - 1;
                else left = mid + 1;
            }
            return left;
        }
    }
}

############

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0, right = 0;
        int sum = 0, res = n + 1;
        while (right < n) {
            sum += nums[right];
            while (sum >= target) {
                res = Math.min(res, right - left + 1);
                sum -= nums[left++];
            }
            ++right;
        }
        return res == n + 1 ? 0 : res;
    }
}

// OJ: https://leetcode.com/problems/minimum-size-subarray-sum/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int sum = 0, i = 0, j = 0, N = nums.size(), ans = INT_MAX;
        while (j < N) {
            while (j < N && sum < s) sum += nums[j++];
            if (sum < s) break;
            while (i < j && sum >= s) sum -= nums[i++];
            ans = min(ans, j - i + 1);
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        s = [0] + list(accumulate(nums))
        n = len(nums)
        ans = n + 1
        for i, v in enumerate(s):
            t = v + target
            j = bisect_left(s, t)
            if j != n + 1:
                ans = min(ans, j - i)
        return 0 if ans == n + 1 else ans

############

class Solution(object):
  def minSubArrayLen(self, target, nums):
    """
    :type target: int
    :type nums: List[int]
    :rtype: int
    """
    sum = 0
    j = 0
    ans = float("inf")
    for i in range(0, len(nums)):
      while j < len(nums) and sum < target:
        sum += nums[j]
        j += 1
      if sum >= target:
        ans = min(ans, j - i)
      sum -= nums[i]
    return ans if ans != float("inf") else 0

func minSubArrayLen(target int, nums []int) int {
	n := len(nums)
	s := make([]int, n+1)
	for i, v := range nums {
		s[i+1] = s[i] + v
	}
	ans := n + 1
	for i, v := range s {
		t := v + target
		left, right := 0, n+1
		for left < right {
			mid := (left + right) >> 1
			if s[mid] >= t {
				right = mid
			} else {
				left = mid + 1
			}
		}
		if left != n+1 && ans > left-i {
			ans = left - i
		}
	}
	if ans == n+1 {
		return 0
	}
	return ans
}

function minSubArrayLen(target: number, nums: number[]): number {
    const n = nums.length;
    let res = n + 1;
    let sum = 0;
    let i = 0;
    for (let j = 0; j < n; j++) {
        sum += nums[j];
        while (sum >= target) {
            res = Math.min(res, j - i + 1);
            sum -= nums[i];
            i++;
        }
    }

    if (res === n + 1) {
        return 0;
    }
    return res;
}

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int n = nums.Length;
        int left = 0, right = 0;
        int sum = 0, res = n + 1;
        while (right < n)
        {
            sum += nums[right];
            while (sum >= target)
            {
                res = Math.Min(res, right - left + 1);
                sum -= nums[left++];
            }
            ++right;
        }
        return res == n + 1 ? 0 : res;
    }
}

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = n + 1;
        let mut sum = 0;
        let mut i = 0;
        for j in 0..n {
            sum += nums[j];

            while sum >= target {
                res = res.min(j - i + 1);
                sum -= nums[i];
                i += 1;
            }
        }
        if res == n + 1 {
            return 0;
        }
        res as i32
    }
}

209 - Minimum Size Subarray Sum

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions