資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
