numbers - 合計が k で割り切れるペアの数を見つけますか?

Question

k の値が与えられます。そのような k<=100000 各ペアの要素の合計が k で割り切れるように、ペアの数を出力する必要があります。^{次の条件では、最初の要素は 2 番目の要素よりも小さく、両方の要素は 10 9}未満である必要があります。

Answer 1

ハッシュ マップを使用した O(N) 時間と O(N) 空間でのソリューション。

コンセプトは次のとおりです。

If (a+b)%k=0 where

a=k*SOME_CONSTANT_1+REMAINDER_1 

b=k*SOME_CONSTANT_2+REMAINDER_2

then (REMAINDER_1 +REMAINDER_2 )%k will surely be 0

したがって、配列 (4,2,3,31,14,16,8) と k =5 の場合、以下のような情報がある場合、すべてのペアの合計 %k =0 を特定できます

一番下の行は、0 から k-1 までのすべての剰余とそれに対応するすべての数字で構成されることに注意してください。あとは、2 つのポインターが合うまで、両方のポインターを互いの方向に移動するだけです。両方のポインターの位置に数値が関連付けられている場合、それらの合計 %k は 0 になります。

これを解決するには、ハッシュ テーブルを使用して、これまでに見たすべての残りを追跡できます。

1. ハッシュ マップ Map<Integer, List> を作成します。
2. そのキーに 0 から k-1 を事前入力します。
3. 配列を反復処理し、各数値の残りを Key = 残りのマップに入れ、実際の数値をリストに入れます。
4. 互いに移動する 2 つのポインターを使用して、キー セットを反復処理します。とsum += listSizeAsPointedByPointer1 * listSizeAsPointedByPointer2