Python程序：查找和为给定值的两段不相交子列表的长度之和

假设我们有一个名为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]，如果找不到则设置为负无穷大

  • last[s] := i

• 对于范围1到N中的i，执行：

  • prefix[i] := prefix[i] 和 prefix[i - 1] 的最小值

• suffix := 大小为N的数组，并用无穷大填充

• last := 一个键值为0时值为N的映射 {0: N}

• s := 0

• 对于范围N - 1到-1中的i（递减），执行：

  • s := s + A[i]

  • suffix[i] := last[s - target] - i （如果找不到则设置为无穷大）

  • last[s] := i

• 对于范围N - 2到-1中的i（递减），执行：

  • suffix[i] := suffix[i] 和 suffix[i + 1] 的最小值

• ans := 对于范围0到N - 1中的每个i，prefix[i] + suffix[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))

输入

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

输出

3

Arnab Chakraborty

更新于：2020年10月21日

95 次浏览

开启您的职业生涯

完成课程获得认证

开始学习