4Sum
整数のリスト nums と整数 target が与えられます。nums の異なる4つの位置にある値を選び、その合計が target となるすべての4つ組 [a, b, c, d] を返してください。各4つ組の値は非減少順に並べてください。同じ4つの値を異なる位置から選べる場合でも、その4つ組は1回だけ含めます。答えは、1番目の値、次に2番目、3番目の順に並べてください。条件を満たす4つ組がない場合は、空のリストを返してください。
関数
- numsinteger-array
- 選択する数値を少なくとも1つ
- targetinteger
- 各4つ組が達成すべき合計
- 戻り値integer-2d-array
- 合計が target となる重複のない4つ組。それぞれをソートし、リスト全体もソートする。該当するものがなければ空のリスト
制約
1 ≤ nums.length ≤ 200-108 ≤ nums[i] ≤ 108-109 ≤ target ≤ 109- 任意の4つの値の合計は
-4 × 108から4 × 108の範囲内に収まるため、32ビット整数で表現できます。 - 同じ4つの値を持つ4つ組は、1つとして数えます。
例
- 入力
- nums = [3, -1, 0, 2, -2, 1, -3]target = 1
- 出力
- [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
- 説明
- 4つの四つ組はそれぞれ合計が1になります。たとえば、
-3 + (-1) + 2 + 3です。-3で始まる2つが最初に来て、2番目の値の順に並びます。つまり、-1が0より先です。
- 入力
- nums = [4, 4, 4, 4, 4, 4]target = 16
- 出力
- [[4, 4, 4, 4]]
- 説明
- 6つの位置から4つを選ぶ15通りのすべてで、4つの4の合計は16になるため、
[4, 4, 4, 4]は1回現れます。
- 入力
- nums = [1, 5, 2, 9]target = 3
- 出力
- []
- 説明
- 唯一の選択肢は4つの数字すべてで、
1 + 5 + 2 + 9 = 17であり、3ではないので、答えは空のリストです。
発展問題
targetになる4つの位置の組の数を数えてください。異なる4つ組の数ではありません。2つ目の例は15です。O(n²)でできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
まずリストを並べ替えます。同じ値は隣り合い、左から選んだ任意の4つの値は、減少しない順になります。
最初の2つの値、
nums[i]とnums[j]（i < j）を固定します。残るのは、jの右側にあるソート済みの値からなるペアで、合計がtarget - nums[i] - nums[j]にならなければなりません。これはソート済みリストに対する Two Sum です。2つのポインターでペアを見つけます。
loはjのすぐ右、hiは最後のインデックスに置きます。目標値より小さい場合はloを右に動かし、大きい場合はhiを左に動かします。ループで直前に試した値と同じ値のiまたはjはスキップし、一致した後は値が変わるまでloを動かし続けます。
解説
4つの位置のすべての組み合わせを確認すると O(n⁴) のコストがかかり、値が重複していると同じ四つ組が何度も生成されます。3Sum への帰着をさらに1段階進めます。ソートし、2つのループで最初の2つの値を固定し、2つのポインターで最後のペアを見つけ、各段階で重複する値をスキップします。
4つのセットをすべて試してください
正しいが、最大のテストでは終わらない
考え方
まずソートして、位置 i < j < k < l の値が非減少順になるようにし、各四つ組が正しい順序で出力されるようにします。4重ループを使うと、4つの位置のあらゆる組み合わせを調べられます。重複を避けるため、次の位置の値が1つ前に試した値と同じ場合、ループを次に進めます。4が6個ある場合、各ループが試すのは最初の位置だけなので、[4, 4, 4, 4] は15回ではなく1回だけ出力されます。
数値が200個の場合、4つの組み合わせは64,684,950通りあり、nが2倍になるとその数は約16倍に増えます。
アルゴリズム
numsをソートします。i < j < k < lの4重ループをネストし、それぞれ外側のループより1つ後から開始します。- 各ループで、ループの最初の位置ではなく、ひとつ前の位置と同じ値を持つ位置をスキップします。
- 4つの値の合計が
targetになったら、[nums[i], nums[j], nums[k], nums[l]]を記録します。ループにより、これらはソートされた順序で生成されます。
def fourSum(nums, target):
nums = sorted(nums)
n = len(nums)
quads = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue # same first value as the round before
for j in range(i + 1, n - 2):
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 - 1):
if k > j + 1 and nums[k] == nums[k - 1]:
continue # same third value as the round before
for l in range(k + 1, n):
if l > k + 1 and nums[l] == nums[l - 1]:
continue # same fourth value as the round before
if nums[i] + nums[j] + nums[k] + nums[l] == target:
quads.append([nums[i], nums[j], nums[k], nums[l]])
return quadsソート、2つのループ、2つのポインター
考え方
nums[i] と nums[j] を固定すると、残るのはペアを探す問題です。つまり、j より右にある値のうち、合計が target - nums[i] - nums[j] になる2つの値を見つけます。ソート済みのリストなら、1回走査するだけで答えが見つかります。lo を j+1 に、hi を最後のインデックスに設定します。合計が target より小さければ lo を右に動かし、大きければ hi を左に動かします。
動かすたびに、どの答えにも含まれない値を1つ除外できます。合計が小さすぎる場合、残っている最大の値 nums[hi] を nums[lo] に足しても不十分なので、nums[lo] を除外できます。合計が大きすぎる場合は、逆の理由で nums[hi] を除外します。1組の (i, j) につき、必要な移動は最大 n 回なので、n²/2 組の計算量は O(n³) です。
最初の例では、i が -3、j が -1 を指しているとき、lo は 0 から 1 を通り過ぎて 2 まで移動し、そこで -3 + (-1) + 2 + 3 = 1 となります。
アルゴリズム
numsをソートします。- 各
iについて、i > 0かつnums[i]がnums[i-1]と等しい場合はスキップします。 iより後の各jについて、j > i+1かつnums[j]がnums[j-1]と等しい場合はスキップします。lo = j+1、hi = n-1に設定します。lo < hiの間、4つの値の合計をtargetと比較します。合計がそれより小さい場合はloを右に、大きい場合はhiを左に動かします。- 一致したら、四つ組を記録し、両方のポインターを動かした後、
loが現在の値を保持している間はloを進めます。
def fourSum(nums, target):
nums = sorted(nums)
n = len(nums)
quads = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue # this first value was already handled
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue # this second value was already handled
lo, hi = j + 1, n - 1
while lo < hi:
total = nums[i] + nums[j] + nums[lo] + nums[hi]
if total < target:
lo += 1
elif total > target:
hi -= 1
else:
quads.append([nums[i], nums[j], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
return quads
落とし穴と境界ケース
nums[j]がnums[j-1]と等しいときにjをスキップすること。j = i+1では、iが使う値と比較するため、target が 8 の場合、[2, 2, 2, 2, 2]から[2, 2, 2, 2]が失われます。- 3Sum の早期終了条件
nums[i] > targetをコピーすること。[-5, -4, -3, -2, -1]で target が -10 の場合、ループは -5 で停止し、[-4, -3, -2, -1]を見落とします。 - 4 個未満のリスト。数値が 1 個または 2 個の場合、
n-3は負になります。Swift では0..<(n - 3)でトラップが発生し、Rust のusizeでn - 3を計算するとアンダーフローします。先に空のリストを返してください。 - 四つ組をハッシュセットに集め、ソートせずに返すこと。
よくある質問3
4Sum の時間計算量はどれくらいですか？
O(n³)。2つのループで約 n²/2 個のペア (i, j) を選び、それぞれに対して最大 n ステップの2ポインター走査を1回行います。O(n log n) のソートは、それに比べるとわずかです。
4SumをkSumに一般化するにはどうすればよいですか？
ソート済みリストに対して kSum(nums, target, k) を記述します。k = 2 の場合は、2ポインターによる走査を行います。k がそれより大きい場合は、先頭の値を順にループし、重複をスキップして、右側の値に対して k-1 と target - nums[i] を指定して自身を呼び出します。各レベルで n の係数が加わるため、kSum の計算量は O(n^(k-1)) です。
4SumはO(n²)で解けますか？
n²/2 個のペアの合計をハッシュマップにまとめ、各ペアを、その合計が自身の合計をtargetから引いた値になるペアと組み合わせることができます。合計を共有するペアが少ない場合は高速ですが、1つの合計に O(n²) 個のペアが含まれることもあるため、最悪の場合は O(n³) より速くなりません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def fourSum(nums, target):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [3, -1, 0, 2, -2, 1, -3] target = 1
期待される出力
[[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]