arr 배열과 다른 값 대상이 있다고 가정합니다. 각각의 합이 target과 같은 두 개의 겹치지 않는 arr의 하위 배열을 찾아야 합니다. 답이 여러 개라면 두 부분배열의 길이의 합이 가장 작은 답을 찾아야 합니다. 두 개의 필수 하위 배열 길이의 최소 합을 찾아야 합니다. 그러한 하위 배열이 없으면 -1을 반환합니다.
따라서 입력이 arr =[5,2,6,3,2,5] target =5와 같으면 출력은 2가 됩니다. 합계가 5인 3개의 하위 배열이 있고 [5], [3,2]입니다. ] 및 [5], 이제 그 중 2개만 크기가 가장 작습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ans :=무한대
-
best :=크기가 arr과 같은 배열을 만들고 무한대로 채웁니다.
-
접두사 :=0
-
최신 :=키 0에 대해 -1을 저장하는 맵
-
rr의 각 인덱스 i와 값 x에 대해 수행
-
접두사 :=접두사 + x
-
(접두사 - 대상)이 최신 항목에 있는 경우
-
ii :=최신[접두사 - 대상]
-
ii>=0이면
-
ans :=ans의 최소값 및 (i - ii + best[ii])
-
-
최고[i] :=나는 - ii
-
-
i가 0이 아니면
-
최신[접두사] :=i
-
-
-
<999999 그렇지 않으면 -1
인 것처럼 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(arr, target):
ans = 999999
best = [999999]*len(arr)
prefix = 0
latest = {0: -1}
for i, x in enumerate(arr):
prefix += x
if prefix - target in latest:
ii = latest[prefix - target]
if ii >= 0:
ans = min(ans, i - ii + best[ii])
best[i] = i - ii
if i: best[i] = min(best[i-1], best[i])
latest[prefix] = i
return ans if ans < 999999 else -1
arr = [5,2,6,3,2,5]
target = 5
print(solve(arr, target)) 입력
[5,2,6,3,2,5], 5
출력
2