나는 다음과 같은 질문을 해결하기 위해 (반드시 코드) 효율적인 알고리즘을 찾고 있어요

Question

가능한 알고리즘으로 요약에게 몇 번을 다시 설정하기 위해 숫자의 주어진 일련의 합산 숫자의 합계가 0 인 경우 누적 합계를 가능한 한 여러 번 0으로 만드는 시작 색인을 찾고 싶습니다.

그것은 특정한 방식으로 일 필요는 없습니다 만, 여기 중요성은 우리가 알고리즘/아이디어가 qudratic "시간 복잡도"

예를 적은 다음이 할 수있을하려는 efficincy-입니다 : 숫자가 주어지면 : 2, -1, 3, 1, -3, -2 :

2 (첫 번째 인덱스)로 합산하면 합계는 0입니다. summation). 그러나 -1로 strting하면 합계 중에 0이 두 번 나타납니다. 주어진 숫자는 하나 이상의 "최상의 색인"을 가질 수 있지만, 우리는 이들 색인 중 적어도 하나를 찾고자합니다.

바이너리 검색을 시도했지만 많은 진전이 없었기 때문에 힌트/도움을 주시면 감사하겠습니다.

Answer 1

프리픽스 합계를 계산할 수 있습니다. 프리픽스 합계의 관점에서, 0은 프리픽스 합계와 동일한 값을 시작 위치로 가지는 위치입니다. 따라서 문제는 접두어 합계의 배열에서 가장 빈번한 요소를 찾는 것으로 감소합니다. 정렬 또는 해시 테이블을 사용하여 효율적으로 해결할 수 있습니다.
입력 : {2, -1, 3, 1, -3, 2}
프리픽스 합 {0, 2, 1, 4, 5, 2, 0}
여기

은 일례이며 가장 빈번한 요소는 2입니다. 2의 첫 번째 발생은 첫 번째 위치에 있습니다. 따라서 두 번째 요소에서 시작하면 최적의 답을 얻을 수 있습니다.