問題

私は先日仕事のためにcodilityテストを受けました。そのため、トレーニングページのいくつかの問題を使って練習してきました リンク

残念ながら、私はTape-Equilibriumの質問で83/100を得ることができました:

N個の整数からなる空のゼロインデックス配列Aが与えられます。配列Aはテープ上の数値を表します。
または このテープを A [0]、A [1]、...、A [P-1]、A [P]、A [P + 1]、...、A [N-1] の二つの空でない部分に分割します。
または 2つの部分の違いは次の値です。 |(A [0] + A [1] + ... + A [P-1])-(A [P] + A [P + 1] + ... + A [N-1])|
または 言い換えれば、第1部の合計と第2部の合計の間の絶対的な違いである。

N個の整数の非空のゼロインデックス配列Aを指定すると、実現可能な最小限の差を返す関数を記述します。

例: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
または このテープを4つの場所に分けることができます。
または P = 1、差= | 3-10 | = 7
または P = 2、差= | 4-9 | = 5
または P = 3、差= | 6-7 | = 1
または P = 4、差= | 10-3 | = 7
または この場合、私はそれが最小の違いであるので1を返します。

nはint、range [2..100,000]です。 Aの各要素はint、range [-1,000..1,000]です。 O(n)時間の複雑さである必要があります。

私のコードは次のとおりです:

 import java.math.*;
class Solution {
public int solution(int[] A) {

    long sumright = 0;
    long sumleft = 0;
    long ans;

    for (int i =1;i<A.length;i++)
        sumright += A[i];

    sumleft = A[0];
    ans =Math.abs(Math.abs(sumright)+Math.abs(sumleft));

    for (int P=1; P<A.length; P++)
    {
        if (Math.abs(Math.abs(sumleft) - Math.abs(sumright))<ans)
            ans = Math.abs(Math.abs(sumleft) - Math.abs(sumright));
        sumleft += A[P];
        sumright -=A[P];
    }
    return (int) ans;  
}
 

私はMath.absに少し怒った。失敗した2つのテスト領域は "double"です(これは-1000と1000の2つの値と "small"です)。 http://codility.com/demo/results/demo9DAQ4T-2HS/

どんな助けもありがとう、私は基本的な間違いをしていないことを確認したい。

  ベストアンサー

あなたの解決策はすでにO(N)です。 absをsumleftとsumrightから削除する必要があります。

 if (Math.abs( sumleft - sumright ) < ans)
{
  ans = Math.abs( sumleft - sumright );
}
 

また、2番目のforループの前に、

 ans =Math.abs( sumleft - sumright );
 

それはうまくいくはずです。

  同じタグがついた質問を見る

javaalgorithmpuzzle