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

pythonserver side programmingprogramming更新于 2025/10/16 2:52:17

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

因此，如果输入为 A = [2, 4, 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 := a 的大小
表 := 一个数组大小为 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
answer := 一个新的集合
对于范围为 1 到 ((S) 的平方根) 的整数部分 + 1，执行
- 如果 S mod i 与 0 相同，则
  - is_present := True
  - part_1 := i
  - part_2 := S / i 的商
  - 对于范围 part_1 到 S + 1 中的 j，在每一步中通过 part_1 进行更新，执行
    - 如果 j 不在 my_map 中，则
      - is_present := False
      - 退出循环
  - 如果 is_present 为真且 part_1 与 S 不同，则
    - 添加(part_1)answer
  - is_present := True
  - 对于 j 在(S / i)到 S + 1 的范围商中，在每个步骤中更新 S // i，执行
    - 如果 j 不在 my_map 中，则
      - is_present := False;
      - 退出循环
  - 如果 is_present 并且 part_2 与 S 不同，则
    - 添加(part_2)answeranswer
如果answer的大小与 0 相同，则
- 返回 -1
返回 answer

示例

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

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))