数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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
95 次浏览
