Problem statement

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

Solution

We can use the fact that all numbers are non-negative and use sliding window approach: we move end pointer if sum is less than target and beg if it is more than target.

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def minSubArrayLen(self, target, nums):
        n = len(nums)
        beg, end, sm, ans = 0, 0, 0, n + 1
        while beg < n:
            if sm < target and end < n:
                sm += nums[end]
                end += 1
            else:
                if sm >= target: ans = min(ans, end - beg)
                sm -= nums[beg]
                beg += 1
        
        return ans if ans != n + 1 else 0

Remark

If we want to have O(n log n) complexity, we can evaluate cumulative sums and then for every Si find minimum Sj such that Sj - Si >= s, j > i with help of binary search.