Try an interactive version of this dialog: Sign up at solve.it.com, click Upload, and pass this URL.
import sys
sys.path.append('.')
from leet_utils import lc_setup, get_leetcode_problem, lc_export
lc_setup("https://leetcode.com/problems/3sum/", add_cells=False)
from IPython.display import HTML
problem = get_leetcode_problem("https://leetcode.com/problems/3sum/")
HTML(problem["content"])
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.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105
import collections
import itertools
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
result = set()
num_to_count = collections.Counter(nums)
# num1 != num2, num1 != num3, and num2 != num3
for num1, num2 in itertools.combinations(num_to_count.keys(), 2):
num3 = -(num1 + num2)
if num1 == num3 or num2 == num3:
continue
if num3 in num_to_count:
result.add(tuple(sorted([num1, num2, num3])))
# num1 == num2, num1 != num3
for num in num_to_count.keys():
if num_to_count[num] < 2:
continue
num3 = -num * 2
if num == num3:
continue
if num3 in num_to_count.keys():
result.add(tuple(sorted([num, num, num3])))
# num1 == num2 == num3
if num_to_count.get(0, 0) >= 3:
result.add((0, 0, 0))
return list(result)
import collections
import itertools
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
result = []
num_to_count = collections.Counter(nums)
unique_nums = sorted(num_to_count)
# num1 < num2 < num3
for num1, num2 in itertools.combinations(unique_nums, 2):
num3 = -(num1 + num2)
if num3 <= num2:
continue
if num3 in num_to_count:
result.append([num1, num2, num3])
# num1 == num2, num1 != num3
for num in unique_nums:
if num_to_count[num] < 2:
continue
num3 = -num * 2
if num == num3:
continue
if num3 in num_to_count:
result.append(sorted([num, num, num3]))
# num1 == num2 == num3
if num_to_count.get(0, 0) >= 3:
result.append([0, 0, 0])
return result
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
sorted_nums = sorted(nums)
result = []
for i in range(len(sorted_nums) - 2):
if i > 0 and sorted_nums[i] == sorted_nums[i - 1]:
continue
left, right = i + 1, len(sorted_nums) - 1
target = -sorted_nums[i]
while left < right:
total = sorted_nums[left] + sorted_nums[right]
if total < target:
left += 1
continue
if total > target:
right -= 1
continue
result.append([sorted_nums[i], sorted_nums[left], sorted_nums[right]])
while left < right and sorted_nums[left] == sorted_nums[left + 1]:
left += 1
while left < right and sorted_nums[right] == sorted_nums[right - 1]:
right -= 1
left += 1
right -= 1
return result
Copied!
{
"id": "toolu_01WnvmdveH9B9RCEZuXnefbA",
"call": {
"function": "read_url",
"arguments": {
"url": "https://github.com/yamashita-ki/codingTest/pull/4"
}
},
"result": "'Skip to content\\n\\n## Navigation Menu\\n\\nToggle navigation\\n\\n[ ](/)\\n\\n[ Sign in ](/login?return_t<TRUNCATED>"
}
Copied!
{
"id": "toolu_01VJs1GtZYUMbqXDbJyM7HS9",
"call": {
"function": "read_url",
"arguments": {
"url": "https://github.com/huyfififi/coding-challenges/pull/30"
}
},
"result": "'Skip to content\\n\\n## Navigation Menu\\n\\nToggle navigation\\n\\n[ ](/)\\n\\n[ Sign in ](/login?return_t<TRUNCATED>"
}
Copied!
{
"id": "toolu_013V8E4tRx88CPJAms6kB1Bi",
"call": {
"function": "read_url",
"arguments": {
"url": "https://github.com/Ryotaro25/leetcode_first60/pull/74"
}
},
"result": "'Skip to content\\n\\n## Navigation Menu\\n\\nToggle navigation\\n\\n[ ](/)\\n\\n[ Sign in ](/login?return_t<TRUNCATED>"
}
各PRの内容を簡潔にまとめます：
PR 1: yamashita-ki/codingTest#4 (Java)
- 解法: 3重ループとtwo pointersの両方を実装
- レビューコメント:
- コードスタイルの揺れ（演算子周りのスペースや
;後のスペース）が気になる - ぶら下がりif（
if (...) break;のように波括弧なし）は事故が起きやすいので避けるべき curSumのcurrentは不要な情報 ― 唯一のsumなので単にsumで十分
- コードスタイルの揺れ（演算子周りのスペースや
PR 2: huyfififi/coding-challenges#30 (Python)
- 解法: Two Sumベースの解法（step1でTLE）、two pointers解法（step2以降）
- レビューコメント:
- 外側ループだけ
fixed_numberと名付けているのは違和感 nums.sort()で入力を変更しているのは問題 ― 呼び出し側が驚く可能性があるので、入力は変更しないか、コメントで明記すべき
- 外側ループだけ
PR 3: Ryotaro25/leetcode_first60#74 (C++)
- 解法: sort + two pointers
- レビューコメント:
sum < 0とsum > 0の場合はcontinueして、sum == 0のネストを下げた方が読みやすいdo-whileを使うと1行減らせる（読みやすさは変わらないかも）numsが非const参照だと変更されると思わせてしまう ― 変更しないならconst参照で渡すべき
共通して参考になるポイント：
- 入力を変更する場合は明示的に（
sorted(nums)を使うなど） - 変数名は冗長な修飾を避ける（
currentなど） - ネストを浅くするために早期
continue/returnを活用
両方のコードを確認しました。
実装2について：
-
2つ目のケースの
sorted()が無駄Copied!result.append(sorted([num, num, num3]))
numとnum3の大小関係を考えると、num3 = -num * 2なので：num < 0→num3 > 0→[num, num, num3]num > 0→num3 < 0→[num3, num, num]
sorted()を使わず、条件分岐で書けます。ただし、その分コードは長くなるのでトレードオフですね。 -
num_to_count.get(0, 0)と他の箇所の一貫性 他ではnum3 in num_to_countを使っているのに、最後だけ.get()を使っています。統一するなら：Copied!if 0 in num_to_count and num_to_count[0] >= 3:
実装3について：
-
PRのレビューで出た「入力変更」の観点
sorted(nums)を使っているので問題なし。良いですね！ -
重複スキップの
whileループに潜在的な問題Copied!while left < right and sorted_nums[left] == sorted_nums[left + 1]: left += 1
left + 1が範囲外になる可能性は？ →left < rightが先に評価されるので大丈夫ですが、left + 1 < len(sorted_nums)の方が意図が明確かもしれません。 -
変数名
totalとtarget両方"t"で始まり、役割が似ているので混乱しやすいかも。current_sumとtarget、あるいはtwo_sumとtargetなど、差別化してもよいかもしれません。 -
early continueパターンの適用（PRで言及されていた点） 現在のコードは十分読みやすいですが、一致した後の処理を関数に切り出すとさらにスッキリする可能性があります。
全体として、実装3はかなり綺麗に書けていると思います。特に気になる点はありますか？
Copied!
def skip_duplicates(start, stop, step):
i = start
while i + step < stop and sorted_nums[i] == sorted_nums[i + step]:
i += step
i += step
return i
こんな感じで、i, left, rightのskip_duplicates操作をまとめたいと思っていますが、これはstep < 0のとき正しく動作しません。 どうやればいいと思う？
良い着眼点ですね！問題は境界チェックの不等号の向きです。
step > 0（left用）:i + step < stopが必要step < 0（right用）:i + step > stopが必要
いくつかのアプローチがあります：
案1: 比較関数を動的に決める
Copied!
def skip_duplicates(start, stop, step):
i = start
in_range = (lambda x: x < stop) if step > 0 else (lambda x: x > stop)
while in_range(i + step) and sorted_nums[i] == sorted_nums[i + step]:
i += step
return i + step
案2: 数学的トリック
Copied!
def skip_duplicates(start, stop, step):
i = start
while (i + step - stop) * step < 0 and sorted_nums[i] == sorted_nums[i + step]:
i += step
return i + step
（stepを掛けることで不等号の向きを揃える）
案3: そもそも別のアプローチ
Copied!
def skip_while_equal(start, step):
i = start
while 0 <= i + step < len(sorted_nums) and sorted_nums[i] == sorted_nums[i + step]:
i += step
return i + step
（stopを渡さず、配列の境界だけチェック。left < rightは呼び出し側で確認）
どのアプローチが好みですか？個人的には案1が意図が明確で読みやすいと思いますが、案3も呼び出し側の責務を明確にする点で悪くないです。
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
sorted_nums = sorted(nums)
n = len(sorted_nums)
result = []
def skip_to_next_different(start, step):
index = start
while (
0 <= index + step < n
and sorted_nums[index] == sorted_nums[index + step]
):
index += step
return index + step
i = 0
while i < n - 2:
j, k = i + 1, n - 1
target = -sorted_nums[i]
# two pointers
# invariant: i < j < k (< n)
while j < k:
total = sorted_nums[j] + sorted_nums[k]
if total < target:
j += 1
continue
if total > target:
k -= 1
continue
result.append([sorted_nums[i], sorted_nums[j], sorted_nums[k]])
j = skip_to_next_different(j, 1)
k = skip_to_next_different(k, -1)
i = skip_to_next_different(i, 1)
return result
とても良いリファクタリングですね！
良い点：
- 関数名
skip_to_next_differentが意図を明確に表現している - 境界チェック
0 <= index + step < nがシンプルで両方向に対応 forからwhileに変えたことで、skip_to_next_differentの使い方が統一されたi,j,kという変数名はtwo-pointers問題で一般的で分かりやすい- invariantコメントがある
細かい改善案：
-
関数の定義位置
skip_to_next_differentはsorted_numsとnをクロージャで参照しています。これ自体は問題ありませんが、テストしやすさを考えると引数で渡す設計もあります（今のままでも十分OK）。 -
条件式の改行スタイル
Copied!while ( 0 <= index + step < n and sorted_nums[index] == sorted_nums[index + step] ):
閉じ括弧と
:の位置が少し珍しいです。以下のどちらかが一般的：Copied!while ( 0 <= index + step < n and sorted_nums[index] == sorted_nums[index + step] ):
または
Copied!while (0 <= index + step < n and sorted_nums[index] == sorted_nums[index + step]):
全体として、元のコードよりかなりスッキリしました。重複スキップのロジックが一箇所にまとまったので、バグが入りにくくなっています。
実装4
- 実装3をベースにリファクタ
- 重複した数字を飛ばす部分を関数化して切り出す。
- ポインタはi, left, rightではなく単にi, j, kにした。
- どうせleft, rightとしてもj, k程度しか情報量はない。（進む向きとかはわからない。）
- ならi, j, kの方が統一感がある。
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
sorted_nums = sorted(nums)
n = len(sorted_nums)
result = []
def skip_to_next_different(start, step):
index = start
while (0 <= index + step < n
and sorted_nums[index] == sorted_nums[index + step]):
index += step
return index + step
i = 0
while i < n - 2:
j, k = i + 1, n - 1
target = -sorted_nums[i]
# two pointers
# invariant: i < j < k (< n)
while j < k:
total = sorted_nums[j] + sorted_nums[k]
if total < target:
j += 1
continue
if total > target:
k -= 1
continue
result.append([sorted_nums[i], sorted_nums[j], sorted_nums[k]])
j = skip_to_next_different(j, 1)
k = skip_to_next_different(k, -1)
i = skip_to_next_different(i, 1)
return result
from IPython.display import Markdown
md = lc_export(
next_url="https://leetcode.com/problems/clone-graph",
dry_run=False,
desc="",
notebook_url="https://share.solve.it.com/d/c560acdd7314a91fab380075345bc406"
)
# Markdown(md)