使用 Python 查找两个非重叠子数组的程序,每个子数组都具有目标总和
假设我们有一个arr数组和另一个值目标。我们必须找到两个不重叠的arr子数组,其中每个子数组的总和等于目标。如果有多个答案,那么我们必须找到一个答案,其中两个子数组的长度之和最小。我们必须找到两个所需子数组长度的最小总和,如果没有这样的子数组,则返回-1。
因此,如果输入类似于arr=[5,2,6,3,2,5]target=5,那么输出将为2三个子数组的总和为5,它们是[5],[3,2]和[5],现在其中只有两个尺寸最小。
为了解决这个问题,我们将按照以下步骤操作-
答:=无穷大
best:=创建一个大小与arr相同的数组并用无穷大填充
前缀:=0
最新:=一个映射,其中为键0存储-1
对于每个索引i和arr的值x,做
最新[前缀]:=i
ii:=最新[前缀-目标]
如果ii>=0,则
最佳[i]:=i-ii
ans:=ans和(i-ii+best[ii])的最小值
前缀:=前缀+x
如果(prefix-target)是最新的,那么
如果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