程序以查找两个非重叠子列表的长度之和，其和在Python中给出

假设我们有一个称为nums的数字列表，另一个值为k，我们必须在nums中找到两个总和为k的不重叠子列表，并且必须找到它们的长度之和。当可能的子列表超过两个时，我们必须找到两个最小的子列表的长度之和。如果找不到答案，则返回-1。

因此，如果输入像nums = [7，10，-2，-1，4，3] k = 7，那么输出将是3，因为我们选择了[7]和[4，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]，如果未找到则设置-infinity

• 最后[s]：=我

• 对于1到N范围内的i

• prefix [i]：=前缀[i]，前缀[i-1]的最小值

• 后缀：=大小N，并用无穷大填充

• last：=键0 {0：N}的值为N的映射

• s：= 0

• 对于范围在N -1至-1的i，减1，

• s：= s + A [i]

• 后缀[i]：= last [s −目标]（如果未找到，设置为无穷大）− i

• 最后[s]：=我

• 对于范围为N − 2至-1的i，减小1，

• 后缀[i]：=后缀[i]和后缀[i +1]的最小值

• ans：=范围0到N − 1中每个i的最小前缀[i] +后缀[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