查找可以在Python中将数组划分为相等总和的子数组的总和

Z时代
2024-01-10
分类：综合

假设我们有一个整数数组A；我们必须找到sum的所有值，以便对于sum [i]值可以将数组划分为sum sum [i]的子数组。如果我们不能将数组划分为相等和的子数组，则返回-1。

因此，如果输入类似于A = [2，4，2，2，2，2，4，2，6]，则输出将为[6,8,12]，因为该数组可以分为以下子数组总和6、8和12。这些如下：[{2，4}，{2，2，2}，{4，2}，{6}] [{2，4，2}，{2，2 ，4}，{2，6}] [{2，4，2，2，2}，{4，2，6

为了解决这个问题，我们将遵循以下步骤-

n：=一个的大小
table：=大小为n并填充0的数组
table [0]：= a [0]
对于1到n范围内的i，执行

table [i]：= a [i] + table [i-1]

S：= table [n-1]
my_map：=新映射
对于0到n范围内的i，执行

my_map [table [i]]：= 1

答案：=一套新的
对于范围1到（(S)的平方根）+ 1的整数部分的i

is_present：=真
part_1：=我
part_2：= S / i的商
对于范围从part_1到S + 1的j，在每一步中由part_1更新，执行
如果is_present为true并且part_1与S不相同，则
is_present：=真
对于（S / i）到S + 1的范围商的j，每步更新S // i，执行
如果is_present并且part_2与S不同，则
is_present：=错误
从循环中出来
如果j不在my_map中，则
添加答案的(part_1)

is_present：=错误;
从循环中出来
如果j不在my_map中，则

添加答案的(part_2)
如果S mod i与0相同，则

如果答案的大小等于0，则

返回-1

返回答案

示例

让我们看下面的实现以更好地理解-

from math import sqrt
def find_sum(a) :
   n = len(a)
   table = [0] * n
   table[0] = a[0]
   for i in range(1, n) :
      table[i] = a[i] + table[i - 1]
   S = table[n - 1]
   my_map = {}
   for i in range(n) :
      my_map[table[i]] = 1
   answer = set()
   for i in range(1, int(sqrt(S)) + 1) :
      if (S % i == 0) :
         is_present = True;
         part_1 = i
         part_2 = S // i
         for j in range(part_1 , S + 1, part_1) :
            if j not in my_map :
               is_present = False
               break
         if (is_present and part_1 != S) :
            answer.add(part_1)
         is_present = True
         for j in range(S // i , S + 1 , S // i) :
            if j not in my_map:
               is_present = False;
               break
         if (is_present and part_2 != S) :
            answer.add(part_2)
   if(len(answer) == 0) :
      return -1
   return answer
a = [2, 4, 2, 2, 2, 4, 2, 6]
print(find_sum(a))