3sum

質問する

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
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]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

最初の試み:

ネストされたforゲートを3つ用いて回転した結果,時間内に発見された.(for i... for j... for k....)

二次試行:

プールメソッド

がソート(sorted())された後、リスト要素に1つずつアクセスします.

規格が確立された2つ:l、r.

2479172標準で+1,-1を選択すると、リスト内の巡回勘定科目および0の要素が検索されます.

と0の要素が見つかった場合、resultに追加されます.

の要素の重複を回避するコードを記述します.

最後に、リストを巡回させるために、l、rの両方が1つずつ移動するコードを記述する.

に答える

def threeSum(nums):
    new_num = sorted(nums)
    length = len(new_num)

    result = []
    
    for i in range(length - 2):
        
        if i > 0 and new_num[i] == new_num[i - 1]:
            continue

        l = i + 1 
        r = length - 1

        while l < r:
            total = new_num[i] + new_num[l] + new_num[r]
            
            if total < 0:
                l += 1

            elif total > 0:
                r -= 1

            elif total == 0:
                result.append([new_num[i], new_num[l], new_num[r]])
                
                while l < r and new_num[l] == new_num[l+1]:
                    l += 1
                    
                while l < r and new_num[r] == new_num[r-1]:
                    r -= 1

                l += 1
                r -= 1

    return result

leetcodeディスカッションで見つけたコード .

推奨事項:

numsがいずれも0の場合、[0,0,0]が返されます.
nums要素が3つ未満の場合、空のリストが返されます.