합계가 K 이상인 최단 하위 배열

정수 배열 nums 과 정수 k 가 주어지면 nums 의 가장 짧고 비어 있지 않은 하위 배열의 길이를 반환합니다. 이때 합은 최소 k 입니다. 그러한 하위 배열이 없으면 -1 를 반환합니다.

하위 배열은 배열의 연속 부분입니다.

예 1:

입력: 숫자 = [1], k = 1
출력: 1

예 2:

입력: 숫자 = [1,2], k = 4
출력: -1

예 3:

입력: 숫자 = [2,-1,2], k = 3
출력: 3

제약:

1 <= nums.length <= 105

-105 <= nums[i] <= 105

1 <= k <= 109

해결책:

from collections import deque

# class Solution:
#     def shortestSubarray(self, nums: List[int], k: int) -> int:
#         n = len(nums)
#         currSum = 0
#         sumTill = [currSum]
#         currSmallest = (0, n + 1)
#         for num in nums:
#             currSum += num
#             sumTill.append(currSum)
#         for i in range(n + 1):
#             for j in range(i + 1, n + 1):
#                 if sumTill[j] - sumTill[i] >= k:
#                     if (j - i) < currSmallest[1] - currSmallest[0]:
#                         currSmallest = (i, j)
#                 if (j - i) >= currSmallest[1] - currSmallest[0]:
#                     break
#         diff = currSmallest[1] - currSmallest[0]
#         if diff == n + 1:
#             return -1
#         else:
#             return diff

# class Solution:
#     def shortestSubarray(self, nums: List[int], k: int) -> int:
#         n = len(nums)
#         currSum = 0
#         sumTill = [currSum]
#         for num in nums:
#             currSum += num
#             sumTill.append(currSum)
#         for j in range(1, n + 1):
#             for i in range(n + 1 - j):
#                 if sumTill[i + j] - sumTill[i] >= k:
#                     return j
#         return -1

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        currSum = 0
        sumTill = [currSum]
        for num in nums:
            currSum += num
            sumTill.append(currSum)
        minLen = n + 1
        q = deque()
        for i, s in enumerate(sumTill):
            while q and s <= sumTill[q[-1]]:
                q.pop()
            while q and s - sumTill[q[0]] >= k:
                minLen = min(minLen, i - q.popleft())
            q.append(i)
        if minLen == n + 1:
            return -1
        return minLen