問題
整数のnums と、target をnums のtarget に
- 答えに
なる組は、 ちょうど 1 組だけある ものとします - 同じ
位置の 数を 2 回使う ことは できません。 同じ 値が 別の 位置に 2 つ あれば、 その 2 つは使えます numsの長さは 2 以上 10000 以下、 値は どれも 絶対値が 10 億以下です
入力と出力の例
例 1
入力
nums = [3, 8, 12, 5]
target = 17出力
[2, 3]例 2
同じ値でも、
入力
nums = [6, 1, 6]
target = 12出力
[0, 2]例 3
負の
入力
nums = [-4, 10, 7, 2]
target = 3出力
[0, 2]面接での聞かれ方
面接では、
- 「整数の
配列と 目標の 数が あります。 足して 目標に なる 2 つの 位置を 返してください」 - 書き終えた
あとに 「いまの 書き方の 計算量は？」 「もっと 速く できますか？」と 続けて 聞かれます - 「答えが
無い ときは どうしますか？」と、 問題文に 無い 場合を 聞かれる こともあります
最初の
まず
段 1
まずはi と、j を 2 重のtarget に
段 2
全部のtarget から
段 3
すぐにdict、Map) を
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def pair_with_target(
nums, target
):
seen = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
j = seen[need]
return [j, i]
seen[x] = i
return []JavaScript
JavaScript
function pairWithTarget(
nums, target
) {
const seen = new Map();
const n = nums.length;
for (let i = 0; i < n; i++) {
const x = nums[i];
const need = target - x;
if (seen.has(need)) {
const j = seen.get(need);
return [j, i];
}
seen.set(x, i);
}
return [];
}答えはreturn [] に
計算量
- 時間は O(n) です。
並びを 前から 1 回なめ、 辞書を 調べるのも 書き足すのも、 平均して 一定の 手間で済みます - 使う
記憶は O(n) です。 最悪の 場合、 ほぼ 全部の 数を 辞書に覚えます - 段 1 の 2 重の
繰り返しは、 時間が O(n²)、 記憶は O(1) です。 記憶を 使う 代わりに 時間を 縮めた、という 取り 引きに なっています
よく
- 先に
書き足してから調べる。 seen[x] = iを先に 置くと、 targetがちょうど xの 2 倍のとき、 自分 自身を 相手として 見つけてしまいます。 例 2 の [6, 1, 6]で 6 を 1つしか 使わずに 答えたことになります - 値で
並べ替えてから探す。 並べ替えると 元の 位置が 分から なくなります。 並べ替えるなら、 位置を 組に して 持ち歩く 必要があります - 返す順を
気にしない。 辞書から 取り出した 位置は、 いま見ている 位置より 必ず前なので、 [seen[need], i]の順に 返せば 小さい 順になります
面接での
書き始める
「まず、
全部の 組を 試す 書き方なら O(n²) で 解けます。 ただ、 1 つ目の 数が 決まると 相手の 数も 決まるので、 見た 数を 辞書に 覚えておけば、 並びを 1 回なめるだけで 探せます。 時間は O(n) で、 その 代わりに 記憶を O(n) 使います。」
書き終えたら、
「例 2 の
[6, 1, 6]でたどります。 最初の 6 では 相手の 6 が まだ 辞書に 無いので、 6 は 0 番と 書き足します。 1 も 同じく 書き足します。 最後の 6 で 相手の 6 が 辞書に あり、 0 番なので [0, 2]を返します。 調べてから 書き足しているので、 同じ 6 を 2 回使う ことは ありません。」