Codilityアルゴリズム試験(三)
上篇の博文に続いて、第三のテーマ.
A non-empty zro-inndexed array A consisting of N positve integers is given.A pair of indices(P,Q)、such that 0<=P<=N,is caled a slice of array A.The sum of a slice(P,Q)is the total of A[P]+A[P＋1]++A[Q].The equi-3 pair is a pair of indices(X,Y)、such that 0思考:このテーマは個人的に一番難しいところです.時間の複雑さはO(N)です.何度も比較すると、複数の要素の和がありますので、入れ子サイクルは避けられないようです.その後他のアルゴリズムを見て、テクニックを習って複雑さを下げました.
A non-empty zro-inndexed array A consisting of N positve integers is given.A pair of indices(P,Q)、such that 0<=P<=N,is caled a slice of array A.The sum of a slice(P,Q)is the total of A[P]+A[P＋1]++A[Q].The equi-3 pair is a pair of indices(X,Y)、such that 0
public int solution(int[] A) {
int sum = 0, leftsum = 0, midsum = 0, rightsum = 0;
int n = A.length;
int[] sums = new int[n];
for (int i=0; i<n; i++) {
sum += A;
sums = sum;
}
int left = 1, right = n - 2;
while (left+1 < right) {
leftsum = sums[left-1];
midsum = sums[right-1] - sums[left];
rightsum = sums[n-1] - sums[right];
if ((leftsum == midsum) && (midsum == rightsum)) {
return 1;
} else if (leftsum > rightsum) {
right--;
} else if (leftsum < rightsum){
left++;
} else {
left++;
right--;
}
}
return 0;
}