三和算法解決方案

Question

原問題聲明：

給定一個n個整數的數組S，是否存在S中的元素a，b，c使得a + b + c = 0？查找數組中所有唯一的三元組，它們的總和爲零。

注意：解決方案集不能包含重複的三元組。

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

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

你好，我解決了上本文給出了兩個和問題一段時間回來，我想用它來解決這三個總和爲好。我的想法是，每個元素找到剩餘列表* -1到0取得該款項高達元素然而兩個元素，此代碼不通過所有測試，例如

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 

原題：https://leetcode.com/problems/3sum/description/

的一個我用來解決這個問題：https://leetcode.com/problems/two-sum/description/

Answer 1

使用itertools。

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）時間複雜度，並傳遞本文給出了測試。它計數出現次數，然後對(number, count)元組進行排序，因此[-1, 0, 1, 2, -1, -4]變爲[(-4, 1), (-1, 2), (0, 1), (1, 1), (2, 1)]。然後它從開始挑選開始迭代，如果可能的話，首先嚐試挑選每個數字兩倍和三分之一，然後將其添加到結果中。然後它挑選一次號碼，並嘗試找到總計爲0的兩個更大的數字。

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