使用Python查找两个非重叠子数组,每个子数组具有目标总和的程序

使用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

    • 如果在latest中存在(prefix−target),则

      • 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程