合計の入れ替え Cracking The Coding Interview
問題
２つの整数配列が与えられる。それぞれの配列から１つずつ要素を決め、それらを交換した時に２つの配列の要素の合計値が一致するようなペアを見つける問題。
入力: {4, 1, 2, 1, 1, 2} と {3, 6, 3, 3}
出力: {1, 3}
解法
全列挙の解法 O(A*B)
i, jを添え字にしてforループを２つネストすることで２つの配列における全ての要素の組合せを得られる。i, jをスワップさせた時に合計値が一致すればそれらを出力する。この解法の計算量は(O(A*B)) (２つの配列のサイズをそれぞれ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)。
