【LeetCode】15. 3Sum 解答・解説【Python】

問題
1. 原文
2. 内容
方針
1. 前提
2. 実装のイメージ
解答
1. 解答1：2ポインタ
2. 解答2
補足・参考・感想

問題

原文

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.

1
2
3
4
5
6
7
8

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.

1
2
3

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.

1
2
3

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 3000

-10⁵ <= nums[i] <= 10⁵

内容

整数配列numsが与えられます。i,j,kが全て異なり、nums[i],nums[j],nums[k]の合計が0になる組み合わせを返してください。

※i,j,kは配列numsの中で全て異なる要素である必要はありますが、値は同じ場合もあります。

※正しくない可能性があります。

方針

前提

実装のイメージ

・解答1：2ポインタを使用します。

→3つの数字の組み合わせの内、1つ目の数字は配列numsに対して端から順番に処理することで走査する。

→3つの数字の組み合わせの内、残り2つの数字は、2ポインタで左右から狭めながら問題の条件を満たす組み合わせを調べる

解答

解答1：2ポインタ

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #ソート
        nums = sorted(nums)
        #resultを準備。set型
        result = set()
        for i in range(len(nums)):
            #leftにはi＋1個目の要素をポインタとして代入
            left = i + 1
            #rightは右端の要素をポインタとして代入
            right = len(nums) - 1
            #targetに0からi番目の要素を引いた数を代入。
            target = 0 - nums[i]
            #leftがrightよりも小さい場合
            while left < right:
                #左右のポインタが指す要素の合計がtargetと一致する場合
                if nums[left] + nums[right] == target:
                    #resultにその組み合わせを追加
                    result.add((nums[i], nums[left], nums[right]))
                    #leftを右に、rightを左に移動
                    #両方とも内側にずらす理由：同じ値が複数あるかもしれないが、
                    #同じ数の組み合わせは1つだけという条件があるから？
                    left += 1
                    right -= 1
                #左右のポインタが指す要素の合計がtargetよりも小さい場合
                #numsは昇順にソートされているので、2つの合計がtargetよりも小さい場合は、
                #左ポインタの値を右にずらして合計値を大きくする
                elif nums[left] + nums[right] < target:
                    #print("nums[i]",nums[i],"target",target,"left",left,"right",right,"nums",nums)
                    #print("nums[left]",nums[left],"nums[right]",nums[right])
                    #leftを一つ右にずらす
                    left += 1
                #左右のポインタが指す要素の合計がtargetよりも大きい場合
                #numsは昇順にソートされているので、2つの合計がtargetよりも大きい場合は、
                #→ポインタの値を左にずらして合計値を大きくする                
                else:
                    #print("nums[i]",nums[i],"target",target,"left",left,"right",right,"nums",nums)
                    #print("nums[left]",nums[left],"nums[right]",nums[right])
                    #rightを一つ左にずらす
                    right -= 1
        #resultをlistにして返す
        return list(result)

class Solution:

def threeSum(self, nums: List[int]) -> List[List[int]]:

#ソート

nums = sorted(nums)

#resultを準備。set型

result = set()

for i in range(len(nums)):

#leftにはi＋1個目の要素をポインタとして代入

left = i + 1

#rightは右端の要素をポインタとして代入

right = len(nums) - 1

#targetに0からi番目の要素を引いた数を代入。

target = 0 - nums[i]

#leftがrightよりも小さい場合

while left < right:

#左右のポインタが指す要素の合計がtargetと一致する場合

if nums[left] + nums[right] == target:

#resultにその組み合わせを追加

result.add((nums[i], nums[left], nums[right]))

#leftを右に、rightを左に移動

#両方とも内側にずらす理由：同じ値が複数あるかもしれないが、

#同じ数の組み合わせは1つだけという条件があるから？

left += 1

right -= 1

#左右のポインタが指す要素の合計がtargetよりも小さい場合

#numsは昇順にソートされているので、2つの合計がtargetよりも小さい場合は、

#左ポインタの値を右にずらして合計値を大きくする

elif nums[left] + nums[right] < target:

#print("nums[i]",nums[i],"target",target,"left",left,"right",right,"nums",nums)

#print("nums[left]",nums[left],"nums[right]",nums[right])

#leftを一つ右にずらす

left += 1

#左右のポインタが指す要素の合計がtargetよりも大きい場合

#numsは昇順にソートされているので、2つの合計がtargetよりも大きい場合は、

#→ポインタの値を左にずらして合計値を大きくする

else:

#print("nums[i]",nums[i],"target",target,"left",left,"right",right,"nums",nums)

#print("nums[left]",nums[left],"nums[right]",nums[right])

#rightを一つ左にずらす

right -= 1

#resultをlistにして返す

return list(result)

解答2

補足・参考・感想

■補足

■参考

前：11. Container With Most Water

次：977. Squares of a Sorted Array

LeetCode 解答・解説記事一覧