Matsushita's Blog

合計の入れ替え Cracking The Coding Interview

問題

2つの整数配列が与えられる。それぞれの配列から1つずつ要素を決め、それらを交換した時に2つの配列の要素の合計値が一致するようなペアを見つける問題。

入力: {4, 1, 2, 1, 1, 2} と {3, 6, 3, 3}
出力: {1, 3}

解法

全列挙の解法 O(A*B)

i, jを添え字にしてforループを2つネストすることで2つの配列における全ての要素の組合せを得られる。i, jをスワップさせた時に合計値が一致すればそれらを出力する。この解法の計算量は(O(A*B)) (2つの配列のサイズをそれぞれA, Bとする)

O(A + B)の解法

実は、配列Aから交換する要素が決定されれば、配列B内の交換するべき要素の候補は決定する。配列A, Bの総和をsumA, sumBとし、それぞれの配列内の交換するべき要素をa, bと置くと。 sumA - a + b = sumB - b + aが成り立つ。あとはaだけを全列挙すればbが決定されるので、計算して得たbが配列B内に存在するかをチェックしてあげれば良い。この解法の計算量はO(A + B)。

ソースコード