用 Python 编写程序，求出两个不重叠子列表的长度和，其和为给定值

pythonserver side programmingprogramming更新于 2026/2/4 16:44:17

假设我们有一个名为 nums 的数字列表和另一个值 k，我们必须在 nums 中找到两个不重叠的子列表，其和为 k，并且我们必须求出它们的长度和。当有两个以上的可能子列表时，我们必须求出两个最小子列表的长度和。如果我们找不到答案，则返回 −1。

因此，如果输入为 nums = [7, 10, −2, −1, 4, 3] k = 7，则输出将为 3，因为我们选择了 [7] 和 [4, 3] 这样的子列表。我们没有选择 [10, −2, −1]，因为这比较长。

为了解决这个问题，我们将遵循以下步骤 −

N := A 的大小
prefix := 大小为 N，并用无穷大填充
last := 键为 0 且值为 −1 的映射 {0: −1
s := 0
对于范围为 0 到 N 的 i，执行
- s := s + A[i]
- prefix[i] := i − last[s − target]，如果未找到，则设置 −infinity
- last[s] := i
对于范围为 1 到 N 的 i，执行
- prefix[i] := prefix[i] 和 prefix[i − 1] 的最小值
suffix := 大小为 N，并用无穷大填充
last := 键为 0 且值为 N 的映射 {0: N
s := 0
对于范围为 N 的 i − 1 到 −1，减少 1，执行
- s := s + A[i]
- suffix[i] := last[s − target](如果未找到则设置无穷大)− i
- last[s] := i
对于范围 N − 2 到 −1 中的 i，减少 1，执行
- suffix[i] := suffix[i] 和 suffix[i + 1] 的最小值
ans := prefix[i] + suffix[i + 1] 的最小值，对于范围 0 到 N − 中的每个 i 1
如果 ans < 无穷大，则返回 ans，否则 −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))