「配列の中から、和が0になる3つ組を全て見つける。ただし重複は禁止」
入力 nums = [-1, 0, 1, 2, -1, -4]
まず昇順にソートします。
元配列: [-1, 0, 1, 2, -1, -4]
ソート後: [-4, -1, -1, 0, 1, 2]
for i = 0 から n-3までループ
各iについて、残り2つを2ポインタで探索します。
leftポインタ:i+1（左から順に）rightポインタ: 配列の最後
和が0になるか判定します。
i = 0 (nums[i] = -4)
left -> index 1 (nums[left] = -1)
right -> index 5 (nums[right] = 2)
sum = -4 + (-1) + 2 = -3
→ 小さいのでleftを右に移動
次：
i = 0
left -> index 2 (nums[left] = -1)
right -> index 5 (nums[right] = 2)
sum = -4 + (-1) + 2 = -3
→ また小さいのでleft++
次：
i = 0
left -> index 3 (nums[left] = 0)
right -> index 5 (nums[right] = 2)
sum = -4 + 0 + 2 = -2
→ 小さいのでleft++
次：
i = 0
left -> index 4 (nums[left] = 1)
right -> index 5 (nums[right] = 2)
sum = -4 + 1 + 2 = -1
→ 小さいのでleft++
left >= right になったのでループ終了
→ 解なし
i = 1 (nums[i] = -1)
left -> index 2 (nums[left] = -1)
right -> index 5 (nums[right] = 2)
sum = -1 + (-1) + 2 = 0
[-1, -1, 2]
[-4, -1, -1, 0, 1, 2]
^ ^ ^
i left right
sum = -1 + -1 + 2 = 0
解を追加したら、 同じ数字はスキップします。
while left < right && nums[left] == nums[left+1]:
left++
while left < right && nums[right] == nums[right-1]:
right--
次の組み合わせを探します。
left -> index 3 (nums[left] = 0)
right -> index 4 (nums[right] = 1)
sum = -1 + 0 + 1 = 0
[-1, 0, 1]
他のiについても同様に探索。
重複を避けながら、すべての3つ組を見つける。
[[-1, -1, 2],
[-1, 0, 1]]
┌──────────────┐
│ 配列をソート │
└──────┬───────┘
│
┌───────▼────────┐
│ i を 0～n-3まで │
└───────┬────────┘
│
┌─────▼─────┐
│ left=i+1 │
│ right=n-1 │
└─────┬─────┘
│
┌──────────▼──────────┐
│ sum=nums[i]+nums[left]+nums[right] │
└──────────┬──────────┘
│
┌──────┴──────┐
┌───▼───┐ ┌────▼────┐
│ sum=0 │ │ sum≠0 │
└───┬───┘ └────┬────┘
│ │
┌───▼───┐ ┌────▼────┐
│ 解追加 │ │ ポインタ更新 │
└───┬───┘ └─────────┘
│
┌───▼───┐
│ 重複除去 │
└───┬───┘
│
▼
次の探索
| 処理 | 計算量 |
|---|---|
| ソート | O(NlogN) |
| 2ポインタ探索 | O(N²) |
- ソート+2ポインタ法で効率的に3Sumを解決
- 重複除去が重要（ソート後だから可能）
- 全探索O(N³) ではなく O(N²) で解ける！