数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 Python 中查找数组可以划分为和相等子数组的所有和
假设我们有一个整数数组 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 的大小
table := 一个大小为 n 并填充 0 的数组
table[0] := a[0]
对于 i 从 1 到 n，执行
table[i] := a[i] + table[i - 1]
S := table[n - 1]
my_map := 一个新的映射
对于 i 从 0 到 n，执行
my_map[table[i]] := 1
answer := 一个新的集合
对于 i 从 1 到 (S 的平方根) 的整数部分 + 1，执行
如果 S 模 i 等于 0，则
is_present := True
part_1 := i
part_2 := S / i 的商
对于 j 从 part_1 到 S + 1，每次更新步长为 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 添加到 answer 中
如果 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))输入
[2, 4, 2, 2, 2, 4, 2, 6]
输出
{8, 12, 6}
99 次查看
