問題
整数のnums を
- 組は
数の 値で 見ます。 値が 同じ 3 つの 組は、 選んだ 位置が 違っても 1 回だけ返します - 返す順は
次の とおりに 決めます。 各組の 中は 小さい 順に 並べます。 組どうしは、 1 つ目の 数が 小さい 組を 先にし、 1 つ目が 同じなら 2 つ目が 小さい 組を 先にします - 足して 0 に
なる 組が 無ければ、 空の 並び []を返します numsの長さは 3 以上 3000 以下、 値は どれも -100000 以上 100000 以下です
入力と出力の例
例 1
入力
nums = [3, -2, 1, -1, 0, -3]出力
[[-3, 0, 3], [-2, -1, 3],
[-1, 0, 1]]例 2
同じ-2 を 2 回使う組は-2 が 2 つある
入力
nums = [-2, 1, 1, 1, 0, 2, -2]出力
[[-2, 0, 2], [-2, 1, 1]]例 3
入力
nums = [5, -1, 7, 2]出力
[]面接での聞かれ方
面接では、
- 「配列から、
足して 0 に なる 3 つの 組を 全部返してください。 同じ組は 重複させないでください」 - 「同じ
値が 何個も 入っていたら？」 「組の 中や 組どうしの 順は？」と、 こちらから 確かめるのを 待たれています。 聞かずに 書き始めると、 重なりの 扱いで 後戻りします - 全部の
組を 試す 書き方を 見せると、 「O(n³) より 速く できますか？」と続きます - 並べ替えと
ツーポインタで 書くと、 「重複を どう 飛ばしましたか？ 飛ばしすぎて 答えを 落としませんか？」と、 飛ばし方の 理由を 聞かれます。 ここが いちばん 詰められる所です - 「集合 (セット) に
入れて 重複を 消すのでは だめですか？」と、 別の 書き方との 比べを 聞かれます - 最後に
「O(n²) より 速く できますか？」 「4 つの組なら？」 「目標が 0 でなく 任意の 数なら？」と、 広げた 形を 聞かれる こともあります
O(n²) より
アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。
まず
段 1
まずは
段 2
1 つ目のa を-a にa よりa の
段 3
並べ替えておくと、a はa、
段 4
重なりを、
- 1 つ目の
数 aに同じ値を 2 回選ぶとき。 並べ替えた 並びで aが 1 つ前と同じ 値なら、 その値で 作れる 組は、 1 つ前の aのときに 全部見つけ終わっています。 1 つ前の aは、いまより 1 つ 広い 範囲 (いまの 範囲と、 いまの a自身) から相手を 探したからです。 だから 飛ばして よいのです - 組を 1 つ
見つけた あと、 左の 指の 値が 同じまま 進むとき。 aと左の 値 bが決まれば、 残りの 値は -a - bに決まります。 同じ bで探し直しても 同じ 組しか 出ないので、 bと違う 値に 来るまで 左の 指を進めます
右のb より
段 5
最後に、a が 0 よりa 以上
解答
Python
Python
def three_sum(nums):
xs = sorted(nums)
n = len(xs)
out = []
for i in range(n):
a = xs[i]
if a > 0:
break
if i > 0:
if a == xs[i - 1]:
continue
lo = i + 1
hi = n - 1
while lo < hi:
b = xs[lo]
c = xs[hi]
total = a + b + c
if total < 0:
lo += 1
continue
if total > 0:
hi -= 1
continue
trip = [a, b, c]
out.append(trip)
hi -= 1
while (
lo < hi
and xs[lo] == b
):
lo += 1
return outJavaScript
JavaScript
function threeSum(nums) {
const xs = [...nums].sort(
(p, q) => p - q
);
const n = xs.length;
const out = [];
for (let i = 0; i < n; i++) {
const a = xs[i];
if (a > 0) {
break;
}
if (i > 0) {
if (a === xs[i - 1]) {
continue;
}
}
let lo = i + 1;
let hi = n - 1;
while (lo < hi) {
const b = xs[lo];
const c = xs[hi];
const total = a + b + c;
if (total < 0) {
lo++;
continue;
}
if (total > 0) {
hi--;
continue;
}
out.push([a, b, c]);
hi--;
while (lo < hi &&
xs[lo] === b) {
lo++;
}
}
}
return out;
}Go
Go
import "sort"
func threeSum(
nums []int,
) [][]int {
xs := append(
[]int{}, nums...,
)
sort.Ints(xs)
n := len(xs)
out := [][]int{}
for i := 0; i < n; i++ {
a := xs[i]
if a > 0 {
break
}
if i > 0 && a == xs[i-1] {
continue
}
lo, hi := i+1, n-1
for lo < hi {
b, c := xs[lo], xs[hi]
total := a + b + c
if total < 0 {
lo++
continue
}
if total > 0 {
hi--
continue
}
out = append(out,
[]int{a, b, c})
hi--
for lo < hi &&
xs[lo] == b {
lo++
}
}
}
return out
}どのnil ではout を [][]int{} で
計算量
- 時間は O(n²) です。
並べ替えが O(n log n)、 1 つ目の 数の 選び方が n 通りで、 それぞれツーポインタが O(n) です。 重なりを 飛ばす繰り返しも 左の 指を 進めるだけなので、 この O(n) に 含まれます - 使う
記憶は、 並べ替えた 写しの O(n) です。 返す組の ぶんは 数えていません。 並びを その場で 並べ替えて よいなら、 写しは 要りません - 段 1 の
全部の 組を 試す 書き方は O(n³) で、 重なりを 消す集合に 最悪 O(n²) の 記憶も要ります - 2 つ目と 3 つ目を
辞書で 探す 書き方も O(n²) ですが、 重なりの 消し方が 難しくなり、 返す順も 別に 並べ直す必要があります
よく
- 1 つ目の
数を、 1 つ後ろと 比べて飛ばす。 xs[i] == xs[i + 1]で飛ばすと、 同じ値の 最初の 方を 飛ばしてしまいます。 [-1, -1, 2]では、1 つ目の -1を飛ばし、 2 つ目の -1からは右に 2しか残らないので、 [-1, -1, 2]を落とします。 1 つ前と 比べれば、 同じ値の うち最初の 1 回は 必ず試されます - 左の
指を、 組を 見つける 前から飛ばす。 繰り返しの 頭で 「左の 値が 1 つ後ろと 同じなら 進める」と 書くと、 [-2, 1, 1]の1と1のように、同じ値を 2 つ 使う 組を 落とします。 飛ばすのは 組を 見つけた あとだけです - 飛ばす繰り返しに
lo < hiを付け忘れる。 [0, 0, 0, 0]では、組を 見つけた あとに 左の 指が 全部の 0 を 進み、 並びの 外を 読んで 止まります。 Python と Go は エラーで 止まり、 JavaScript は undefinedを読んでも 黙って 進むので 気づきにくくなります - 重なりを
飛ばさず、 最後に 集合で消す。 答えは 合いますが、 組の 数ぶんの 記憶を 余分に 使い、 返す順も 並べ直しが 要ります。 面接では 「なぜ飛ばしてよいか」を 言えないまま 逃げた、と 受け取られがちです - JavaScript で
sort()に比べる 関数を 渡さない。 数が 文字として 並ぶので、 [10, 9, -1]は[-1, 9, 10]ではなく[-1, 10, 9]と並び、 ツーポインタの 前提が 崩れます。 (p, q) => p - qを渡します - 1 つ目の
数の 繰り返しの 中で、 2 つの 指を 外に置く。 loとhiをaごとに作り直さないと、 前の aで進めた 指から 始まり、 組を 落とします
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「同じ値の
組は 1 回だけ、 組の 中は 小さい 順、 組どうしも 小さい 順で 返す、で よいですか。 全部の 組を 試すと O(n³) です。 並べ替えてから 1 つ目の 数を 左から 固定すると、 残りは 並んだ 範囲で 足して -aになる 2 つを 探す問題に なるので、 両端からの ツーポインタで O(n) で 探せます。 全体は O(n²) です。 重なりは 2 か所で 消します。 1 つ目が 1 つ前と 同じ 値なら、 その組は 1 つ前で 見つけ終わっているので 飛ばします。 組を 見つけたら、 左の 指を 違う 値まで 進めます。 右は 和が 大きくなるので 自然に 戻ります。」
書き終えたら、
「例 2 は
並べ替えると [-2, -2, 0, 1, 1, 1, 2]です。1 つ目の -2で、0 と 2 の 組と、 1 と 1 の 組が 見つかります。 1 と 1 を 見つけた あと、 左の 指は 1 を 通り過ぎて、 右の 指と 出会って 終わります。 2 つ目の -2は 1 つ前と同じなので 飛ばします。 0 から 先は、 右に 足して 0 に なる 相手が 無いまま 終わります。 だから [[-2, 0, 2], [-2, 1, 1]]です。」