1. Problem
209. 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.
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^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
2. Solution
I solved this problem like this.
2.1. Time over solution
- I first solved this problem like this.
- I check all length of sum and this time complexity is O(n^2).
- n’s max value is 10^5, so this makes problem.
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
for l in range(1, len(nums)+1):
value = sum(nums[:l])
# check value
if value >= target:
return l
for i in range(0, len(nums)-l):
# value change
value = value - nums[i] + nums[i+l]
# check value
if value >= target:
return l
return 0
2.2. Good solution
- This solution used ‘Sliding window’. I I was greatly helped by AnthonyChao’s solution. Thank you so much!
- This solution works like this. The time complexity is just O(n).
- If
sum between right and left >= target, move left cursor - Else, move right cursor.
[2,3,1,2,4,3] total = 2, left = 0, right = 0, ans = 987654321
^
[2,3,1,2,4,3] total = 5, left = 0, right = 1, ans = 987654321
^ ^
[2,3,1,2,4,3] total = 6, left = 0, right = 2, ans = 987654321
^ ^
[2,3,1,2,4,3] total = 8, left = 0, right = 3, ans = 4
^ ^
[2,3,1,2,4,3] total = 6, left = 1, right = 3, ans = 4
^ ^
[2,3,1,2,4,3] total = 10, left = 1, right = 4, ans = 4
^ ^
[2,3,1,2,4,3] total = 7, left = 2, right = 4, ans = 4
^ ^
[2,3,1,2,4,3] total = 6, left = 3, right = 4, ans = 4
^ ^
[2,3,1,2,4,3] total = 9, left = 3, right = 5, ans = 4
^ ^
[2,3,1,2,4,3] total = 7, left = 4, right = 5, ans = 2
^ ^
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
ans = 987654321
left, total = 0, 0
for right in range(len(nums)):
total += nums[right]
while total >= target:
ans = min(ans, right - left + 1)
total -= nums[left]
left += 1
return ans if ans != 987654321 else 0