Chương trình tìm tổng độ dài hai danh sách con không chồng chéo có tổng bằng giá trị cho trước trong Python

Giả sử chúng ta có một danh sách các số gọi là nums và một giá trị k, chúng ta phải tìm hai danh sách con (sublists) không chồng chéo trong nums có tổng bằng k, và tìm tổng độ dài của chúng. Khi có nhiều hơn hai danh sách con khả thi, chúng ta phải tìm tổng độ dài của hai danh sách con nhỏ nhất. Nếu không tìm thấy đáp án, trả về -1.

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

Để giải quyết, chúng ta thực hiện các bước sau:

• N := kích thước của A
• prefix := mảng kích thước N, điền bằng vô cực
• last := map với giá trị -1 cho khóa 0 {0: -1}
• s := 0
• với i trong khoảng 0 đến N:
  • s := s + A[i]
  • prefix[i] := i - last[s - target], nếu không tìm thấy đặt -vô cực
  • last[s] := i
• với i trong khoảng 1 đến N:
  • prefix[i] := min(prefix[i], prefix[i - 1])
• suffix := mảng kích thước N, điền bằng vô cực
• last := map với giá trị N cho khóa 0 {0: N}
• s := 0
• với i từ N - 1 xuống -1, giảm 1:
  • s := s + A[i]
  • suffix[i] := last[s - target] (nếu không tìm thấy đặt vô cực) - i
  • last[s] := i
• với i từ N - 2 xuống -1, giảm 1:
  • suffix[i] := min(suffix[i], suffix[i + 1])
• ans := min(prefix[i] + suffix[i + 1]) cho mỗi i trong khoảng 0 đến N - 1
• trả về ans nếu ans < vô cực, ngược lại -1

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

Input

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

Output

3