← 전체 회차
A-012● Day 122026.05.14mediumleetcode #15neetcode150

3Sum

#array#two-pointers#sorting
↗ leetcode #15 · 3sum
01

문제

· problem
P.012

3Sum

↗ leetcode #15

정수 배열 nums가 주어질 때, i != j, i != k, j != k이고 nums[i] + nums[j] + nums[k] == 0을 만족하는 모든 삼중쌍(triplet) [nums[i], nums[j], nums[k]]을 반환하세요. 주의: 결과 집합은 중복된 삼중쌍을 포함하면 안 됩니다.

제약
  • · 3 ≤ nums.length ≤ 3000
  • · -10^5 ≤ nums[i] ≤ 10^5
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[-1,0,1,2,-1,-4]
[[-1, -1, 2], [-1, 0, 1]]
example 2input → output
[0,1,1]
[]
example 3input → output
[0,0,0]
[[0, 0, 0]]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    결과 삼중쌍들을 임의의 순서로 반환해도 되나요?
  • ☐
    '중복된 삼중쌍'이 정확히 무엇을 의미하나요?
  • ☐
    풀이 중에 입력 배열을 수정해도 되나요?
  • ☐
    한 삼중쌍에서 같은 배열 원소를 여러 번 사용할 수 있나요?
  • ☐
    배열의 인덱스를 반환해야 하나요, 아니면 값을 반환해야 하나요?
  • ☐
    항상 해가 존재하나요?
  • ☐
    알고리즘에서 음수를 특별히 처리해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 결과 리스트 초기화
○
res = []
○
res = {}
○
res = set()
step 2· 배열 정렬
○
nums.sort()
○
nums = sorted(set(nums))
○
nums.sort(reverse=True)
step 3· 외부 포인터로 배열 반복
○
for i, a in enumerate(nums):
○
for i in range(len(nums) - 2):
○
for i, a in enumerate(nums[:-1]):
step 4· 양수를 조기에 건너뛰기│ 중첩
○
if a > 0:
○
if a > 0:
    continue
○
if a >= 0:
    break
step 5· 고정된 원소의 중복 값 건너뛰기│ 중첩
○
if i > 0 and a == nums[i - 1]:
○
if i > 0 and a == nums[i + 1]:
    continue
○
if a in seen:
    continue
seen.add(a)
step 6· 내부 탐색을 위한 투 포인터 설정│ 중첩
○
l, r = i + 1, len(nums) - 1
○
l, r = 0, len(nums) - 1
○
l, r = i + 1, i + 2
step 7· 삼중쌍 추가 및 중복 쌍 건너뛰기│ │ 중첩
○
res.append([a, nums[l], nums[r]])
○
res.append([a, nums[l], nums[r]])
l += 1
○
res.append([a, nums[l], nums[r]])
l += 1
r -= 1
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def threeSum(self, nums: List[int]) -> List[List[int]]:
3
        res = []
4
        nums.sort()
5
6
        for i, a in enumerate(nums):
7
            # Skip positive integers
8
            if a > 0:
9
                break
10
11
            if i > 0 and a == nums[i - 1]:
12
                continue
13
14
            l, r = i + 1, len(nums) - 1
15
            while l < r:
16
                threeSum = a + nums[l] + nums[r]
17
                if threeSum > 0:
18
                    r -= 1
19
                elif threeSum < 0:
20
                    l += 1
21
                else:
22
                    res.append([a, nums[l], nums[r]])
23
                    l += 1
24
                    r -= 1
25
                    while nums[l] == nums[l - 1] and l < r:
26
                        l += 1
27
                        
28
        return res
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[-1,0,1,2,-1,-4]
→
[[-1, -1, 2], [-1, 0, 1]]
case 2
[0,1,1]
→
[]
case 3
[0,0,0]
→
[[0, 0, 0]]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.