TIL #70 : [Algorithm] LeetCode 15. 3sum

6645 ワード
TIL コセット leetcode algorithm テキストリンク

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つ未満の場合、空のリストが返されます.
    Delphiフォルダ選択ダイアログ(新規フォルダボタンあり)修正版
    Opengl惑星システム