Pythonで3Sum問題を解く：合計が0になる3つの数の組み合わせを見つけるアルゴリズム

整数型の配列が与えられ、その中に a + b + c = 0 を満たす3つの要素 a、b、c が存在するとします。この条件を満たすすべての一意なトリプレット（3つ組）を見つけるのが、古典的なアルゴリズム問題「3Sum」です。

例えば、配列が [-1, 0, 1, 2, -1, -4] の場合、答えは [[-1, -1, 2], [-1, 0, 1]] となります。同じ数字の組み合わせが重複して出力されない点に注意してください。

解法のアプローチ

この問題を効率的に解くには、ソート＋双方向ポインタ（Two Pointers）という手法を用います。手順は以下の通りです。

• 配列 nums を昇順にソートし、結果を格納する配列 res を定義する
• i を 0 から（nums の長さ − 3）まで繰り返す
  • i > 0 かつ nums[i] == nums[i-1] の場合は重複を避けるためスキップして次へ進む
  • 左ポインタ l = i + 1、右ポインタ r = len(nums) - 1 とする
  • l < r の間、以下を繰り返す
    • sum = nums[i] + nums[l] + nums[r] を計算する
    • sum < 0 なら l += 1、sum > 0 なら r -= 1 とする
    • sum == 0 の場合は [nums[i], nums[l], nums[r]] を res に追加する
    • 重複を排除するため、隣接する同じ値をスキップしながらポインタを移動させる
    • 最後に l += 1、r -= 1 として次の組み合わせを探索する
• すべての探索が終わったら res を返す

Pythonでの実装例

以下のコードは上記のアルゴリズムを実装したものです。

class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        result = []
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i+1
            r = len(nums)-1
            while(l<r):
                sum = nums[i] + nums[l] + nums[r]
                if sum<0:
                    l+=1
                elif sum >0:
                    r-=1
                else:
                    result.append([nums[i],nums[l],nums[r]])
                    while l<len(nums)-1 and nums[l] == nums[l + 1]: l += 1
                    while r>0 and nums[r] == nums[r - 1]: r -= 1
                    l+=1
                    r-=1
        return result
ob1 = Solution()
print(ob1.threeSum([-1,0,1,2,-1,-4]))

入力例

[-1,0,1,2,-1,-4]

出力例

[[-1,-1,2],[-1,0,1]]

計算量について

このアルゴリズムの時間計算量は O(n²) です。外側のループで各要素を固定し、内側で双方向ポインタにより線形時間で探索するため、全組み合わせを総当たりする O(n³) よりも大幅に高速化できます。空間計算量については、ソートに O(log n)、出力を除けば O(1) の追加メモリで済みます。LeetCodeなどのコーディング面接でも頻出の問題なので、ぜひマスターしておきましょう。