数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用Python查找两个和为目标值的互不重叠子数组的程序
假设我们有一个数组arr和另一个值target。我们必须找到arr的两个互不重叠的子数组，每个子数组的和都等于target。如果有多个答案，那么我们必须找到两个子数组长度之和最小的答案。如果不存在这样的子数组，则返回-1。
因此，如果输入类似于arr = [5,2,6,3,2,5] target = 5，则输出将为2，因为存在三个和为5的子数组，它们是[5]，[3,2]和[5]，其中只有两个子数组具有最小的长度。
为了解决这个问题，我们将遵循以下步骤：
ans := 无穷大
best := 创建一个与arr大小相同的数组，并用无穷大填充
prefix := 0
latest := 一个映射，其中键0的值为-1
对于arr的每个索引i和值x，执行：
prefix := prefix + x
如果(prefix - target)存在于latest中，则：
ii := latest[prefix - target]
如果ii >= 0，则：
ans := ans和(i - ii + best[ii])的最小值
best[i] := i - ii
如果i非零，则：
latest[prefix] := i
如果ans < 999999，则返回ans；否则返回-1
让我们来看下面的实现以更好地理解：
示例
def solve(arr, target):
ans = 999999
best = [999999]*len(arr)
prefix = 0
latest = {0: -1}
for i, x in enumerate(arr):
prefix += x
if prefix - target in latest:
ii = latest[prefix - target]
if ii >= 0:
ans = min(ans, i - ii + best[ii])
best[i] = i - ii
if i: best[i] = min(best[i-1], best[i])
latest[prefix] = i
return ans if ans < 999999 else -1
arr = [5,2,6,3,2,5]
target = 5
print(solve(arr, target))输入
[5,2,6,3,2,5], 5
输出
2
更新于：2021年5月29日
浏览量：176
广告