[Problem] Minimum Size Subarray Sum

Problem Statement

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

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.

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

Since the subarray [4, 3] is equal to or greater than 7, hence it satisfies the problem condition where we return 2 as our answer.

The problem involves two parts:

1. Prefix sum to quickly measure the sum within the subarray
2. Sliding window to go through all of the possible combinations

여기서 prefix sum 자체는 필수적이지는 않다. 물론 문제 자체는 편해지지만, prefix sum없이 sliding windows 만 사용해도 풀수 있는 문제지만, 배운 컨셉을 위해서 강제?적으로 넣어서 풀어보았다.

def minSubArrayLen(self, target, nums):
        p_sum = [0] + nums
        for i in range(1, len(p_sum)): p_sum[i] += p_sum[i - 1]

        right = 0
        min_len = float('inf')
        for left in range(1, len(p_sum)):
            while right < len(p_sum) and p_sum[right] - p_sum[left - 1] < target:
                right += 1
            if right < len(p_sum) and p_sum[right] - p_sum[left - 1] >= target:
                min_len = min(min_len, right - left + 1)

        if min_len == float('inf'): return 0
        return min_len

문제 풀이 자체는 저번 sliding window 문제 (Move Zeroes)와 비슷한데, 여기서 추가적으로 prefix sum을 사용하여 subarray 안의 합을 구하는 것을 최대한 쉽게 만들었다. Hence, the sliding windows algorithm is again used to measure all the possible subarrays within O(n) time complexity. The problem can also be solved using binary search, but it is less efficient with a time complexity of O(n log(n)), and hence will not be used for this problem.