정수 A의 배열이 있다고 가정합니다. sum[i] 값에 대해 배열이 sum sum[i]의 하위 배열로 나눌 수 있도록 sum에 대한 모든 값을 찾아야 합니다. 배열을 동일한 합계의 하위 배열로 나눌 수 없으면 -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으로 채워진 배열
-
테이블[0] :=a[0]
-
범위 1에서 n까지의 i에 대해 수행
-
테이블[i] :=a[i] + 테이블[i - 1]
-
-
S :=테이블[n - 1]
-
my_map :=새 지도
-
0에서 n 사이의 i에 대해 수행
-
my_map[테이블[i]] :=1
-
-
답변 :=새로운 세트
-
범위 1에서 ((S)의 제곱근) + 1의 정수 부분까지 i에 대해
-
S mod i가 0과 같으면
-
is_present :=참
-
part_1 :=나는
-
part_2 :=S / i의 몫
-
범위 part_1에서 S + 1까지의 j에 대해 각 단계에서 part_1씩 업데이트합니다.
-
j가 my_map에 없으면
-
is_present :=거짓
-
루프에서 나오다
-
-
-
is_present가 true이고 part_1이 S와 같지 않으면
-
답변의 추가(part_1)
-
-
is_present :=참
-
(S / i) ~ S + 1의 범위 몫에 있는 j에 대해 S // i씩 각 단계에서 업데이트하고
-
j가 my_map에 없으면
-
is_present :=거짓;
-
루프에서 나오다
-
-
-
is_present 및 part_2가 S와 같지 않으면
-
답변 추가(part_2)
-
-
-
-
답변의 크기가 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)) 입력
[2, 4, 2, 2, 2, 4, 2, 6]
출력
{8, 12, 6}