は（しかし、私がタイムアウトにすべてのテストに合格しない、私はJavaとI出力正しい値に<strong><a href="https://www.hackerrank.com/challenges/playing-with-numbers/problem" rel="nofollow noreferrer">THIS</a></strong><strong>Hackerrank</strong>問題を解決しようとしていますループ

Question

FOR複数と時間の複雑さを改善するための最良の方法は何です巨大な入力）私は7 "FOR" LOOPSを持ってしまったので、私はプログラミングの新種であることをお勧めできます、これらのループを減らすための最良の方法は何ですか。ループは次のようにします。

ループ1：すべての空間で入力を分割し、String配列
ループ2に各値を代入：はintに文字列を変換とのint型バージョンに各int値を割り当て計算
ループ3を可能にする配列、：クエリ入力用繰り返しループ1が、今回
ループ4： REPEATループ2、今回クエリ入力用
ループ5： OUTERループはovに行くえー、各Q
ループ6：ループ5の内部ループ1の各配列値の上に移動して、CURRクエリ値とCURR値を合計する
ループ7：更新の上に行くためのループ5の内部ループ2配列の値とそれらの絶対値を最初に取得することによってそれらを合計します。

です。非常に多くのループの後、複雑さは災害です。任意のアイデアをどのように改善するのですか？

Answer 1

時間の複雑さは、ほとんどの場合、最後のネストされたループまで下がります。すべてのクエリと配列全体を繰り返し処理すると、反復回数が多くなりすぎます（100000 * 100000 = 10000000000）。これらの配列を繰り返し処理する必要がありますが、ネストされた方法で処理する必要はありません。任意のクエリ内で約log(100000)回の繰り返ししか行えません。問題ページは、対数であるバイナリ検索のヒントです。

入力は、[1, -2, 3]というクエリを持つ[-1, 2, -3]の配列です。

配列の順序は任意であるため、配列を並べ替えて[-3, -1, 2]になるようにすることができます。

最初のクエリ1では、配列[-2, 0, 3]が得られます。そこここで、配列を反復するための十分な時間がありませんので、代わりに答えは、最初の配列と異なる方法を考える：

• 2が3に変更されているので、合計は1によって増加します。陽性のまま残っている数字は同じ増加を示します。

• -3は-2に変化したので、合計は1減少します。負のままの数字は同じ減少を示します。

• は0に変更されているため、合計は1だけ減少します。これは上記と同様です。

• ここには記号を変更する数字はありませんが、それらに何が起こるかを確認してください。配列がソートされている場合、それらはすべて配列内の隣接する値になります。ここでは、元の配列内の値の範囲の合計を知るのに役立ちます。これらは、配列の各接頭辞の合計を格納することによって事前に計算できます。

あなたは[2, 5, 0]の配列に問題を変換することができるように、すべての数字で始まることが陽性であった場合、それは容易かもしれ注意と[-3, 1, -2, 3]を照会し、出力は最初の答えがありません。

元の配列の合計が6なので、新しい合計は6 + 1 - 1 - 1 = 5です。正または負の数（バイナリ検索を試みる）がどれくらいあるかを知っていれば、それぞれの和は数回の乗算、加算、減算に過ぎません。