3Sum
整数のリスト nums が与えられます。nums の異なる3つの位置から選んだ値の組で、a + b + c = 0 を満たすすべての三つ組 [a, b, c] を見つけてください。各三つ組を非減少順（a ≤ b ≤ c）に並べ、位置の選び方が複数あっても、異なる三つ組はそれぞれ1回だけ列挙してください。三つ組を最初の値、次に2番目の値の順に並べて返してください。
関数
- numsinteger-array
- 少なくとも3つの要素を含む整数のリスト
- 戻り値integer-2d-array
- 合計が0になる、それぞれの異なる3つ組を、各組を非減少順に並べ、リスト全体もソートする
制約
3 ≤ nums.length ≤ 3000-105 ≤ nums[i] ≤ 105- 少なくとも1つの三つ組の合計は0になります。
- 2つの三つ組は、同じ3つの値を持つとき、同じです。
例
- 入力
- nums = [-2, 0, 1, 1, -1, 2]
- 出力
- [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
- 説明
- -2 + 0 + 2、-2 + 1 + 1、-1 + 0 + 1 はすべて 0 になります。1 は 2 つの位置にあるため、
[-2, 1, 1]では値 1 を 2 回使えますが、[-1, 0, 1]はどちらの 1 を使っても作れ、1 回だけ現れます。
- 入力
- nums = [0, 0, 0, 0]
- 出力
- [[0, 0, 0]]
- 説明
- 4つのゼロのうちどの3つを選んでも、合計は0になります。選ぶ位置は4通りありますが、どれも同じ組み合わせになるため、答えには
[0, 0, 0]が1回だけ含まれます。
提出時に隠しテスト+15件
発展問題
同じパターンで4Sumを解けます。2つの値を固定し、残りの要素に対して2つのポインターを使います。O(n³)で実装し、すべての段階で重複の処理を正しく行えますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
まずリストをソートします。ソートされたリストには2つの利点があります。各3つ組が順番に並び、同じ値が隣り合うため、重複する値は必ず元の値のすぐ後ろに並びます。
トリプレットの最小値である
nums[i]を固定します。残りの2つの値の和は-nums[i]でなければならず、それらはiの右側にあるソート済みの値から選びます。これはソート済みリストにおけるペアの和を求める問題です。その組み合わせでは、一方のポインターを
iのすぐ右に、もう一方を最後のインデックスに置きます。3つの値の合計が0未満なら左のポインターを右へ動かし、0より大きければ右のポインターを左へ動かします。一致したら両方を動かし、左のポインターが同じ値の重複分を通り過ぎるようにします。値が直前の値と等しいiはスキップします。
解説
3Sumが見た目より難しいのは、2つの理由があります。すべての3つ組を調べるにはO(n³)かかり、値が重複していても、答えには各3つ組を1回だけ含めなければなりません。ソートすれば、両方の問題を解決できます。同じ値が隣り合うので、隣同士を比較して重複を飛ばせます。また、最小の値を固定すると、残りの2つはソート済みリスト上のペアの和の問題になり、2つのポインターを使って一度の走査で解けます。
すべての三つ組を試す
正しいが、最大のテストでは終わらない
考え方
まずリストをソートします。すると、任意の3つの位置 i < j < k の値はすでに順序どおりになり、nums[i] ≤ nums[j] ≤ nums[k] となるため、トリプレットは見つけた時点で正しく書き出されます。3重ループですべての位置の組み合わせを調べるので、見逃すトリプレットはありません。
次に、重複への対処です。最初の例をソートすると [-2, -1, 0, 1, 1, 2] となり、[-1, 0, 1] の1にはインデックス3またはインデックス4の値を使えます。そこで各ループでは、そのループで直前に試した値と同じ値を持つ位置をスキップします。すると各ループはそれぞれ異なる値を一度ずつ試し、異なる各トリプレットはソート済みの順序で一度ずつ得られます。スキップ時に比較するのは同じループ内の直前の位置だけなので、[-2, 1, 1] では引き続き2つの1を使えます。
問題は計算量です。組み合わせは約 n³/6 個あり、3000個の数値では合計の計算が4.5 × 10^9回になります。これはどのような制限時間もはるかに超えます。
アルゴリズム
numsをソートします。- 各位置について
iをループし、nums[i]がnums[i-1]と等しい場合はiをスキップします。 - その中で、
i+1からjをループし、j > i+1かつnums[j]がnums[j-1]と等しい場合はjをスキップします。 - その中でさらに、同じスキップ規則を使って
j+1からkをループし、3つの値の合計が 0 の場合は[nums[i], nums[j], nums[k]]を記録します。 - 見つけた順に三つ組を返します。すでにソートされています。
def threeSum(nums):
nums = sorted(nums)
n = len(nums)
triplets = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # same first value as the round before
for j in range(i + 1, n - 1):
if j > i + 1 and nums[j] == nums[j - 1]:
continue # same second value as the round before
for k in range(j + 1, n):
if k > j + 1 and nums[k] == nums[k - 1]:
continue # same third value as the round before
if nums[i] + nums[j] + nums[k] == 0:
triplets.append([nums[i], nums[j], nums[k]])
return triplets1つの値を固定し、ハッシュセットでペアを見つける
考え方
最初の値 nums[i] を固定したら、合計が -nums[i] になる、それより後ろの2つの値が必要です。これが Two Sum です。j を i の右側へ進め、通過した値を集合に保持します。各 j で、不足している値は need = -nums[i] - nums[j] です。need が集合にあれば、[nums[i], need, nums[j]] の合計は 0 になります。集合の検索は平均 O(1) で済むため、1つの i につき O(n)、探索全体では O(n²) です。
ソートによって重複の管理もできます。値が直前の値と等しい i はスキップします。一致が見つかったら、j を nums[j] のコピーをすべて通り過ぎるまで進めます。最初と3番目の値が固定されていれば、真ん中の値も固定されるため、同じ値がもう一つあっても、同じ三つ組が繰り返されるだけです。need はソート済みリストの前の位置から得られるので、need ≤ nums[j] となり、三つ組は順序どおりです。また、nums[i] > 0 になった時点で処理を打ち切ることもできます。その後の2つの値はそれ以上の大きさなので、合計が 0 になることはありません。
一点注意があります。j を右へ進めると nums[j] は大きくなり、need は小さくなるため、1つの i に対する三つ組は、真ん中の値が大きい順に出てきます。[-2, -1, 0, 1, 1, 2] で i = 0 の場合、2つ目の 1 で [-2, 1, 1] が見つかり、その後 2 で [-2, 0, 2] が見つかります。答えに追加する前に、各グループを反転してください。C 版と R 版では、ハッシュセットの代わりに、値をインデックスとする配列に既出の値を記録します。すべての値が ±10^5 の範囲内にあるため、この方法が使えます。
アルゴリズム
numsをソートします。- 各
iについて、nums[i] > 0になったら終了し、nums[i]がnums[i-1]と等しい場合はiをスキップします。 - 空の集合を作成します。
i+1から始まる各jについて、need = -nums[i] - nums[j]を計算します。集合にneedが含まれていれば、[nums[i], need, nums[j]]を記録し、nums[j]の重複分を飛ばす位置までjを進めます。 nums[j]を集合に追加し、次のjに進みます。- この
iについて見つかった三つ組を逆順にし、答えに追加します。
def threeSum(nums):
nums = sorted(nums)
n = len(nums)
triplets = []
for i in range(n - 2):
if nums[i] > 0:
break # the two values after it are at least as large
if i > 0 and nums[i] == nums[i - 1]:
continue # this first value was already handled
group = []
seen = set() # values between position i and position j
j = i + 1
while j < n:
need = -nums[i] - nums[j]
if need in seen:
group.append([nums[i], need, nums[j]])
while j + 1 < n and nums[j + 1] == nums[j]:
j += 1
seen.add(nums[j])
j += 1
# need shrinks as nums[j] grows, so this group came out backwards
group.reverse()
triplets.extend(group)
return tripletsソートして2つのポインターを使う
考え方
정렬된 순서로 집합을 대체할 수 있습니다. nums[i]를 고정하고, lo를 i+1에, hi를 마지막 인덱스에 둔 다음 nums[i] + nums[lo] + nums[hi]를 살펴봅니다. 합이 0보다 작으면 더 큰 값이 필요하므로 lo를 오른쪽으로 이동합니다. 0보다 크면 더 작은 값이 필요하므로 hi를 왼쪽으로 이동합니다. 합이 정확히 0이면 세 값의 조합을 기록하고 두 포인터를 모두 이동합니다.
놓치는 세 값의 조합은 없습니다. 합이 0보다 작을 때는 남은 값 중 가장 큰 값인 nums[hi]와 짝지어도 nums[lo]의 값이 부족하므로, 범위 안에 남은 어떤 값과도 짝을 이룰 수 없습니다. 따라서 이를 제외해도 아무것도 놓치지 않습니다. 합이 0보다 클 때는 그 반대입니다. nums[hi]의 값이 남은 값 중 가장 작은 값과 짝지어도 너무 큽니다. 각 단계에서 값 하나を完全に除外するため、1つのiにかかるステップ数は最大nで、探索全体はO(n²)です。必要なメモリはソートと出力以外にありません。
ソート済みの[-2, -1, 0, 1, 1, 2]を見てみましょう。i = 0（値は-2）のとき、loは-1、hiは2から始まります。合計は-1なので、loを0まで進めます。ここで-2 + 0 + 2 = 0となるため、[-2, 0, 2]を記録します。両方のポインターは2つの1の位置に移動し、[-2, 1, 1]が得られます。i = 1（値は-1）のとき、0と2の合計は1なので、hiを2つ目の1まで戻します。すると-1 + 0 + 1 = 0となり、[-1, 0, 1]を記録します。i = 2の値0では何も見つからず、i = 3では値が正なので、探索を終了します。
重複には2つのルールが必要です。値が1つ前と同じiはスキップします。一致が見つかった後は、使用した値のコピーを飛び越えるまでloを進めます。hiには独自のルールは必要ありません。loがより大きな値に移動すると、以前のnums[hi]のコピーでは合計が0を超えるため、それ自体で対象から外れます。iは異なる値を小さい順に調べ、loは右にしか移動しないため、三つ組はソートされた順に並びます。
アルゴリズム
numsをソートします。- 各
iについて、nums[i] > 0になったら停止し、nums[i]がnums[i-1]と等しい場合はiをスキップします。 lo = i+1とhi = n-1を設定します。lo < hiの間、nums[i]、nums[lo]、nums[hi]を合計します。- 合計が 0 未満なら、
loを右に移動します。0 より大きいなら、hiを左に移動します。 - 0 なら、3 つ組を記録し、両方のポインターを移動してから、使用した値の重複分を飛ばすように
loを移動します。 - 3 つ組を返します。すでにソートされています。
def threeSum(nums):
nums = sorted(nums)
n = len(nums)
triplets = []
for i in range(n - 2):
if nums[i] > 0:
break # the two values after it are at least as large
if i > 0 and nums[i] == nums[i - 1]:
continue # this first value was already handled
lo, hi = i + 1, n - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
triplets.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
return triplets
落とし穴と境界ケース
誤答の多くは値の重複が原因なので、重複を含む入力でテストしましょう。
nums[i]がnums[i+1]と等しいときにiをスキップすると、各値の最後のコピーが最初の要素として残り、それより前のコピーはなくなります。[-1, -1, 2]では、[-1, -1, 2]が失われます。ひとつ前の位置にあるnums[i-1]と比較してください。nums[i] > 0ではなくnums[i] ≥ 0のときに停止すると、[0, 0, 0]を見落とします。- 重複をスキップせず、最後に取り除くこと。3000 個のゼロの場合、ツーポインターループは後処理を行う前に
[0, 0, 0]のコピーを何百万個も記録します。また、いくつかの言語ではリストの集合はリストを同一性で比較するため、コピーがそのまま残ってしまいます。 - 同じ位置を2回使うこと。リスト全体をあらかじめ集合に入れるハッシュセット版では、唯一の 1 を2回使って
[-2, 1, 3]が[-2, 1, 1]になります。すでに通過した位置にある値だけを検索してください。 - トリプレットを順不同で返すこと。比較は完全一致なので、ハッシュセット版では各グループを逆順にする必要があり、トリプレットを集合に集める解法では最後にソートする必要があります。
よくある質問4
3Sum の時間計算量はどれくらいですか？
ソートと2つのポインターを使う解法の実行時間は O(n²) です。ソートには O(n log n) かかり、最初の値の n 通りの選択それぞれに O(n) の走査を1回行います。ソートと出力を除けば、追加の領域は O(1) で済みます。すべての三つ組を調べる場合は、代わりに O(n³) かかります。
3Sumはどのようにして重複するトリプレットを回避しますか？
リストをソートするため、等しい値は隣り合います。次に、1つ前の値と等しい値は最初のものをスキップし、一致するたびに左ポインターを、使用した値の複製を越えた位置へ移動します。各トリプレットは、その値の最初の複製から一度だけ見つかるため、結果を格納するセットは必要ありません。
3Sumには、2ポインター法とハッシュセットのどちらを使うべきですか？
どちらも O(n²) 時間で実行されます。2ポインター法では追加のメモリは必要なく、ソート済みの順序によって、トリプレットがすでに順番どおりに得られます。ハッシュセットは O(n) のメモリを使用し、位置が重複しないようにし、出力をソートするための注意が必要です。ハッシュセットの考え方が重要になるのは、元のインデックスを返す Two Sum のように、ソートできない場合です。
3SumはO(n²)より速く解けますか？
大きくはありません。最もよく知られているアルゴリズムでも、n²を上回るのはわずかな対数因子にすぎず、計算幾何学における多くの計算困難性の結果は、2未満のnのべき乗に達するアルゴリズムは存在しないと仮定しています。そうした高速なアルゴリズムは研究成果なので、面接で期待される答えはO(n²)です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def threeSum(nums):
# ここにコードを書いてくださいケース1
ケース2
入力
nums = [-2, 0, 1, 1, -1, 2]
期待値
[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]