3つの合計アルゴリズム解

Question

元の問題文：

n個の整数の配列Sが与えられた場合、a + b + c = 0となるようにSに要素a、b、cがあるか？配列のすべてのユニークなトリプレットを見つけて、ゼロの合計を求めます。

注：ソリューションセットには、重複するトリプレットが含まれていてはなりません。

For example, given array S = [-1, 0, 1, 2, -1, -4], 

A solution set is: [[-1, 0, 1], [-1, -1, 2]] 

こんにちは私はしばらくの間バックLeetCode上の2つの和の問題を解決し、私も3点の合計を解決するためにそれを使用するのではと思いました。私の考えは、すべての要素のための* -1ただし0を取得するための要素を合計まで残り、リスト内の2つの要素を見つけることです、このコードは例

Input: [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6] 
Output: [[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2]] 
Expected: [[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2]] 

のために、すべてのテストに合格していない私は「ドン何が間違っているのか本当に知りません。誰かが私に問題を説明するのに十分な親切な人になれますか？ あなた

class Solution(object): 
    def threeSum(self, nums): 
     """ 
     :type nums: List[int] 
     :rtype: List[List[int]] 
     """ 
     def twoSum(self, nums, target): 
      targ = target 
      for index, i in enumerate(nums): 
       targ -= i 
       if targ in nums[index+1:]: 
        return [nums[index], nums[nums[index+1:].index(targ)+index+1]] 
       else: 
        targ = target 
      return None 
     res = [] 
     for index, i in enumerate(nums): 
      target = i * -1 
      num = nums[:index] + nums [index+1:] 
      ans = twoSum(self, num, target) 
      if ans != None: 
       temp = ans + [i] 
       temp.sort() 
       res.append(temp) 
     print(res) 
     import itertools 
     res.sort() 
     res = list(res for res,_ in itertools.groupby(res)) 
     return res 

オリジナル質問ありがとう：itertoolsを使用してhttps://leetcode.com/problems/two-sum/description/

Answer 1

：私はこれを解決するために使用していhttps://leetcode.com/problems/3sum/description/

ものを。

import itertools 
stuff = [-1, 0, 1, 2, -1, -4] 
stuff.sort() 
ls = [] 
for subset in itertools.combinations(stuff, 3): 
    if sum(list(subset))==0: 
     # first I have sorted the list because of grouping 
     # Ex: [-1, 0, 1] and [0, 1, -1] are build with the same element 
     # so here is avoiding this. 
     if list(subset) not in ls: 
      ls.append(list(subset)) 
print(ls) 

入力/出力

input : [-1, 0, 1, 2, -1, -4] 
output : [[-1, -1, 2], [-1, 0, 1]] 
input : [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6] 
output: [[-4, -2, 6], [-4, 0, 4], [-4, 1, 3], [-4, 2, 2], [-2, -2, 4], [-2, 0, 2]] 

Answer 2

ここはO（n^2）時間複雑性を有するとLeetCode試験に合格することを解決する別の方法です。それは発生をカウントしてから(number, count)タプルをソートするので、[-1, 0, 1, 2, -1, -4]は[(-4, 1), (-1, 2), (0, 1), (1, 1), (2, 1)]になります。それから、最初のピッキングから各数字を2回ピックアップし、可能であれば3番目のピックアップを繰り返し、これを結果に追加します。一度番号を選んで2つの大きい数字を見つけようとします。

from collections import Counter 

class Solution(object): 
    def threeSum(self, nums): 
     res = [] 
     counts = Counter(nums) 
     num_counts = sorted(counts.items()) 

     # Handle the only case where we pick three same nums 
     if counts[0] >= 3: 
      res.append([0] * 3) 

     for i, (first, first_count) in enumerate(num_counts): 
      # Pick two of these and one greater 
      if first_count >= 2 and first < 0 and -(first * 2) in counts: 
       res.append([first, first, -(first * 2)]) 

      # Pick one and two greater 
      for j in range(i + 1, len(num_counts)): 
       second, second_count = num_counts[j] 
       # Pick two of these as second and third num 
       if second_count >= 2 and -first == 2 * second: 
        res.append([first, second, second]) 

       # Pick this as second num and third which is greater 
       third = -(first + second) 
       if third > second and third in counts: 
        res.append([first, second, third]) 

     return res