209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/description/

Difficulty: Medium

This is a typical two pointers (sliding window) problem. The key point is to find the right condition to move the pointers.

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

Python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        p1, p2 = 0, 0
        min_len = float('inf')
        cum_sum = nums[0]
        while p2 < len(nums):
            if cum_sum >= target:
                min_len = min(min_len, p2 - p1 + 1)
                cum_sum -= nums[p1]
                p1 += 1
            else:
                # cum_sum < target
                p2 += 1
                if p2 >= len(nums):
                    break
                cum_sum += nums[p2]
        return min_len if min_len != float('inf') else 0

C++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int p1 = 0, p2 = 0;
        int min_len = nums.size() + 1;
        int cum_sum = nums[0];
        while (p2 < nums.size()) {
            if (cum_sum >= target) {
                min_len = min(min_len, p2 - p1 + 1);
                cum_sum -= nums[p1++];
            } else {
                if (++p2 >= nums.size()) {
                    break;
                }
                cum_sum += nums[p2];
            }
        }
        return min_len != nums.size() + 1 ? min_len : 0;
    }
};

Golang

func minSubArrayLen(target int, nums []int) int {
    p1 := 0
    p2 := 0
    minLen := math.MaxInt32
    cumSum := nums[0]
    for p2 < len(nums) {
        if cumSum >= target {
            minLen = min(minLen, p2 - p1 + 1)
            cumSum -= nums[p1]
            p1++
        } else {
            p2++
            if p2 >= len(nums) {
                break
            }
            cumSum += nums[p2];
        }
    }
    if minLen != math.MaxInt32 {
        return minLen
    }
    return 0
}

Rust

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let mut p1 = 0;
        let mut p2 = 0;
        let mut min_len = i32::MAX;
        let mut cum_sum = nums[0];
        let n = nums.len();
        while p2 < n {
            if cum_sum >= target {
                min_len = std::cmp::min(min_len, (p2 - p1 + 1) as i32);
                cum_sum -= nums[p1];
                p1 += 1;
            } else {
                p2 += 1;
                if p2 >= n {
                    break;
                }
                cum_sum += nums[p2];
            }
        }
        if min_len != i32::MAX { min_len } else { 0 }
    }
}