問題
整数のnums をout をout の i 番目にはnums の i 番目を
- 割り算を
使わずに 解いてください - 時間は O(n) で
解いてください。 n は numsの長さです numsの長さは 2 以上 100000 以下、 値は どれも -30 以上 30 以下です - 途中の
どの 積も、 32 ビットの 符号付き整数に 収まる ものとします
入力と出力の例
例 1
入力
nums = [2, 3, 5, 1]出力
[15, 10, 6, 30]例 2
0 が 1 つあると、
入力
nums = [4, 0, 2, -1]出力
[0, -8, 0, 0]例 3
負の
入力
nums = [-2, -3, 4]出力
[-12, -8, 6]面接での聞かれ方
面接では、
- 「各要素に
ついて、 自分以外の 要素の 積を 並べた 配列を 返してください」 - 全部の
積を 出して 各値で 割る 書き方を 見せると、 「割り算を 使わずに 書けますか？」と続きます - 「0 が
入っていたら、 割り算の 書き方は どうなりますか？」と、 割り算の 弱点を 聞かれます - 書き終えた
あとに 「返す配列の ほかに、 追加の 記憶を O(1) に できますか？」と 詰められる こともあります
割り算の
アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。
まず
段 1
まずは
段 2
i 番目を
段 3
左の
段 4
記憶をout にright でout の
解答
Python
Python
def product_except_self(nums):
n = len(nums)
out = [1] * n
left = 1
for i in range(n):
out[i] = left
left *= nums[i]
right = 1
for i in reversed(range(n)):
out[i] *= right
right *= nums[i]
return outJavaScript
JavaScript
function productExceptSelf(
nums
) {
const n = nums.length;
const out = new Array(n);
let left = 1;
for (let i = 0; i < n; i++) {
out[i] = left;
left *= nums[i];
}
let right = 1;
let i = n - 1;
while (i >= 0) {
out[i] *= right;
right *= nums[i];
i--;
}
return out;
}Go
Go
func productExceptSelf(
nums []int,
) []int {
n := len(nums)
out := make([]int, n)
left := 1
for i := 0; i < n; i++ {
out[i] = left
left *= nums[i]
}
right := 1
for i := n - 1; i >= 0; i-- {
out[i] *= right
right *= nums[i]
}
return out
}どちらの
計算量
- 時間は O(n) です。
前から 1 回、 後ろから 1 回、 並びを なめるだけです - 返す
並びの ほかに 使う 記憶は O(1) です。 leftとrightと番号だけです。 返す 並びも 数えるなら O(n) です - 左の
積と 右の 積を 別々の 並びに 持つ 書き方も O(n) の 時間ですが、 記憶は 並び 2 本ぶん 多く要ります
よく
- 全部の
積を 出して割る。 条件に 反するうえ、 0 が 1 つあると 全部の 積が 0 に なり、 0 の 位置の 答え (残りの 積) が 出せません。 0 が 2 つ あれば 答えは 全部 0 ですが、 これも 場合分けが要ります - 自分を
掛けてから書く。 left *= nums[i]をout[i] = leftより先に 置くと、 自分まで 含んだ積に なります。 例 1 なら 先頭が 15 ではなく 30 になります - 後ろからの
繰り返しで、 out[i]に代入してしまう。 out[i] = rightと書くと、 前の 繰り返しで 入れた 左の 積が 消えます。 ここは 掛け合わせる *=です - JavaScript で
後ろからの 番号を 1 つずらす。 i = nから始めると、 nums[n]がundefinedになり、 そこから 先が 全部 NaNになります
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「位置ごとに
残りを 掛けると O(n²) です。 i を 除いた 積は、 i より 左の 積と 右の 積を 掛けた 物なので、 前から 1 回なめて 左の 積を 返す配列に 書き、 後ろから 1 回なめて 右の 積を 掛け合わせます。 割り算を 使わないので 0 が あっても 場合分けが 要らず、 時間は O(n)、 返す配列の ほかの 記憶は O(1) です。」
書き終えたら、
「例 3 の
[-2, -3, 4]でたどります。 前から なめると、 左の 積は 1、 -2、 6 です。 後ろから なめて 作った 右の 積を、 位置の 順に 並べると -12、 4、 1 です。 位置ごとに 掛けると、 1 と -12 で -12、 -2 と 4 で -8、 6 と 1 で 6 なので、 [-12, -8, 6]です。」