← all entries
A-012● Day 122026.05.14mediumleetcode #15neetcode150

3Sum

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

Problem

· problem
P.012

3Sum

↗ leetcode #15

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

constraints
  • · 3 ≤ nums.length ≤ 3000
  • · -10^5 ≤ nums[i] ≤ 10^5
// paraphrased summary — see source for full text
examples
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

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Can the output triplets be returned in any order?
  • ☐
    What exactly counts as duplicate triplets?
  • ☐
    Can I modify the input array during the solution?
  • ☐
    Can the same array element be used multiple times in a single triplet?
  • ☐
    Should I return array indices or the values themselves?
  • ☐
    Must there always be a solution?
  • ☐
    Are negative numbers treated differently in the algorithm?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize result list
○
res = []
○
res = {}
○
res = set()
step 2· Sort the array
○
nums.sort()
○
nums = sorted(set(nums))
○
nums.sort(reverse=True)
step 3· Iterate through array with outer pointer
○
for i, a in enumerate(nums):
○
for i in range(len(nums) - 2):
○
for i, a in enumerate(nums[:-1]):
step 4· Skip positive numbers early│ nested
○
if a > 0:
○
if a > 0:
    continue
○
if a >= 0:
    break
step 5· Skip duplicate values of the fixed element│ nested
○
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· Set up two pointers for inner search│ nested
○
l, r = i + 1, len(nums) - 1
○
l, r = 0, len(nums) - 1
○
l, r = i + 1, i + 2
step 7· Add triplet and skip duplicate pairs│ │ nested
○
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
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· 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
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
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 does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.