Chương trình tìm tổng độ dài của hai danh sách con không trùng nhau có tổng được đưa ra bằng Python

Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác k, chúng ta phải tìm hai danh sách con không trùng nhau trong num có tổng là k và chúng ta phải tìm tổng độ dài của chúng. Khi có nhiều hơn hai danh sách con, chúng ta phải tìm tổng độ dài của hai danh sách con nhỏ nhất. Nếu chúng tôi không thể tìm thấy câu trả lời, hãy trả về −1.

Vì vậy, nếu đầu vào là nums =[7, 10, −2, −1, 4, 3] k =7, thì đầu ra sẽ là 3, khi chúng ta chọn các danh sách con như [7] và [4, 3] . Chúng tôi đã không chọn [10, −2, −1] vì nó dài hơn.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• N:=kích thước của A

• tiền tố:=của kích thước N và điền vào vô cùng

• last:=một bản đồ có giá trị −1 cho khóa 0 {0:−1}

• s:=0

• đối với tôi trong phạm vi từ 0 đến N, hãy thực hiện

  • s:=s + A [i]

  • tiền tố [i]:=i - last [s - target], nếu không tìm thấy đặt −infinity

  • [s] cuối cùng:=i

• đối với tôi trong phạm vi từ 1 đến N, hãy thực hiện

  • prefix [i]:=tối thiểu của tiền tố [i], tiền tố [i - 1]

• hậu tố:=có kích thước N và điền vào vô cùng

• last:=một bản đồ có giá trị N cho khóa 0 {0:N}

• s:=0

• đối với tôi trong phạm vi N - 1 đến −1, giảm 1, thực hiện

  • s:=s + A [i]

  • hậu tố [i]:=last [s - target] (nếu không tìm thấy thì đặt vô cùng) - i

  • [s] cuối cùng:=i

• đối với tôi trong phạm vi N - 2 đến −1, giảm đi 1, thực hiện

  • hậu tố [i]:=tối thiểu là hậu tố [i] và hậu tố [i + 1]

• ans:=tối thiểu tiền tố [i] + hậu tố [i + 1] cho mỗi i trong phạm vi từ 0 đến N - 1

• trả về ans nếu ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

3