nums라는 숫자 목록과 target이라는 다른 입력이 있다고 가정하면 합계 값이 target과 같거나 더 크도록 가장 짧은 하위 목록의 크기를 찾아야 합니다. 그러한 하위 목록이 없으면 -1을 반환합니다.
따라서 입력이 nums =[2, 11, -4, 17, 4] target =19와 같으면 출력은 2가 됩니다. [17, 4]를 선택하여 최소 19의 합을 얻을 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ps :=요소가 하나만 있는 목록 0
-
숫자의 각 숫자에 대해 수행
-
ps 뒤에 삽입(ps + num의 마지막 요소)
-
num>=target이면
-
1 반환
-
-
-
min_size :=inf
-
q :=[0]
-
j :=0
-
범위 1에서 ps 크기까지의 i에 대해
-
j :=j의 최소값, q의 크기 - 1
-
동안 j
=target, do
-
min_size :=min_size의 최소값 및 (i - q[j])
-
j :=j + 1
-
-
동안 q 및 ps[i] <=ps[q의 마지막 요소], 수행
-
q에서 마지막 요소 삭제
-
-
q 끝에 i 삽입
-
-
-
min_size
이면 min_size를 반환합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution:
def solve(self, nums, target):
ps = [0]
for num in nums:
ps += [ps[-1] + num]
if num >= target:
return 1
min_size = float("inf")
q = [0]
j = 0
for i in range(1, len(ps)):
j = min(j, len(q) - 1)
while j < len(q) and ps[i] - ps[q[j]] >= target:
min_size = min(min_size, i - q[j])
j += 1
while q and ps[i] <= ps[q[-1]]:
q.pop()
q.append(i)
return min_size if min_size < float("inf") else -1
ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target)) 입력
[2, 11, -4, 17, 4], 19
출력
2