파이썬에서 합이 주어진 두 개의 겹치지 않는 하위 목록 길이의 합을 찾는 프로그램

<시간/>

nums라고 하는 숫자 목록과 다른 값 k가 있다고 가정하고 합이 k인 nums에서 두 개의 겹치지 않는 하위 목록을 찾아야 하고 길이의 합을 찾아야 합니다. 두 개 이상의 가능한 하위 목록이 있는 경우 두 개의 가장 작은 하위 목록 길이의 합을 찾아야 합니다. 답을 찾을 수 없으면 -1을 반환합니다.

따라서 입력이 nums =[7, 10, −2, −1, 4, 3] k =7과 같으면 [7] 및 [4, 3]과 같은 하위 목록을 선택할 때 출력은 3이 됩니다. . [10, −2, −1]이 더 길기 때문에 선택하지 않았습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

N :=A의 크기
접두사 :=크기가 N이고 무한대로 채우기
last :=키 0 {0:−1}
에 대해 값이 -1인 맵
s :=0
범위 0에서 N까지의 i에 대해 수행
- s :=s + A[i]
- prefix[i] :=i − last[s − target], 찾을 수 없는 경우 set −infinity
- 마지막[s] :=i
범위 1에서 N까지의 i에 대해 수행
- 접두사[i] :=접두사[i]의 최소값, 접두사[i − 1]
접미사 :=크기 N, 무한대로 채우기
last :=키 0 {0:N}에 대해 값이 N인 맵
s :=0
N − 1 ~ −1 범위의 i에 대해 1 감소, do
- s :=s + A[i]
- suffix[i] :=last[s − target] (찾을 수 없는 경우 무한대 설정) − i
- 마지막[s] :=i
N − 2 ~ −1 범위의 i에 대해 1 감소, do
- suffix[i] :=suffix[i]와 suffix[i + 1]의 최소값
ans :=0 ~ N − 1 범위의 각 i에 대한 접두사[i] + 접미사[i + 1]의 최소값
인 것처럼 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, A, target):
      INF = float("inf")
      N = len(A)
      prefix = [INF] * N
      last = {0: −1}
      s = 0
      for i in range(N):
         s += A[i]
         prefix[i] = i − last.get(s − target, −INF)
         last[s] = i
      for i in range(1, N):
         prefix[i] = min(prefix[i], prefix[i − 1])
      suffix = [INF] * N
      last = {0: N}
      s = 0
      for i in range(N − 1, −1, −1):
         s += A[i]
         suffix[i] = last.get(s − target, INF) − i
         last[s] = i
      for i in range(N − 2, −1, −1):
         suffix[i] = min(suffix[i], suffix[i + 1])
      ans = min(prefix[i] + suffix[i + 1] for i in range(N − 1))
      return ans if ans < INF else −1
ob = Solution()
nums = [7, 10, −2, −1, 4, 3]
k = 7
print(ob.solve(nums, k))

입력

[7, 10, −2, −1, 4, 3], 7