優化解決方案三薩姆

Question

我試圖解決3薩姆問題表述爲：

給定n個整數的數組S，在那裏元件A，B，C在S，從而使A + B + c = 0？查找數組中所有唯一的三元組，它們的總和爲零。

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

這是我的解決這個問題：

def threeSum(nums): 
    """ 
    :type nums: List[int] 
    :rtype: List[List[int]] 
    """ 
    nums.sort() 
    n = len(nums) 
    solutions = [] 
    for i, num in enumerate(nums): 
     if i > n - 3: 
      break 

     left, right = i+1, n-1 
     while left < right: 
      s = num + nums[left] + nums[right] # check if current sum is 0 
      if s == 0: 
       new_solution = [num, nums[left], nums[right]] 
       # add to the solution set only if this triplet is unique 

       if new_solution not in solutions: 
        solutions.append(new_solution) 
       right -= 1 
       left += 1 
      elif s > 0: 
       right -= 1 
      else: 
       left += 1 

    return solutions 

將該溶液正常工作與的O(n**2 + k)時間複雜度和空間的O(k)複雜，其中n是輸入陣列和k的大小是多少的解決方案。

在LeetCode上運行此代碼時，我得到大尺寸數組的TimeOut錯誤。我想知道如何進一步優化我的代碼以通過裁判。

P.S：我已閱讀this related question中的討論。這並沒有幫助我解決問題。

Answer 1

一對夫婦的改進，你可以讓你的算法：

1）使用sets，而不是爲您的解決方案列表。使用一組將確保您沒有任何重複，並且您不必執行if new_solution not in solutions:檢查。

2）爲全零清單添加邊緣案例檢查。沒有太多的開銷，但在某些情況下可以節省大量的時間。

3）將枚舉更改爲第二段時間。它有點快。奇怪的是，我在測試中獲得了更好的性能，並且使用了一個while循環，然後n_max = n -2; for i in range(0, n_max): Reading this xrange或range的問題和答案應該更快。

注：如果我運行測試5次，我不會得到他們中的任何一個相同的時間。我所有的測試都是+ -100毫秒。因此，採取一些鹽優化一些小優化。對於所有的python程序來說，它們可能不會更快。它們可能只會在測試運行的確切硬件/軟件配置上更快。

另外：如果您從代碼中刪除所有評論，那麼HAHAHAH的速度會快300ms。然而，測試正在運行的只是一個有趣的副作用。

我已將O（）符號放入代碼中需要大量時間的所有部分。

def threeSum(nums): 
    """ 
    :type nums: List[int] 
    :rtype: List[List[int]] 
    """ 
    # timsort: O(nlogn) 
    nums.sort() 

    # Stored val: Really fast 
    n = len(nums) 

    # Memory alloc: Fast 
    solutions = [] 

    # O(n) for enumerate 
    for i, num in enumerate(nums): 
     if i > n - 3: 
      break 

     left, right = i+1, n-1 

     # O(1/2k) where k is n-i? Not 100% sure about this one 
     while left < right: 
      s = num + nums[left] + nums[right] # check if current sum is 0 
      if s == 0: 
       new_solution = [num, nums[left], nums[right]] 
       # add to the solution set only if this triplet is unique 

       # O(n) for not in 
       if new_solution not in solutions: 
        solutions.append(new_solution) 
       right -= 1 
       left += 1 
      elif s > 0: 
       right -= 1 
      else: 
       left += 1 

    return solutions 

這裏有一些代碼不會超時並且很快（ish）。這也暗示了一種方法，使算法WAY更快（使用設置多;））

class Solution(object): 
def threeSum(self, nums): 
    """ 
    :type nums: List[int] 
    :rtype: List[List[int]] 
    """ 
    # timsort: O(nlogn) 
    nums.sort() 

    # Stored val: Really fast 
    n = len(nums) 

    # Hash table 
    solutions = set() 

    # O(n): hash tables are really fast :) 
    unique_set = set(nums) 
    # covers a lot of edge cases with 2 memory lookups and 1 hash so it's worth the time 
    if len(unique_set) == 1 and 0 in unique_set and len(nums) > 2: 
     return [[0, 0, 0]] 

    # O(n) but a little faster than enumerate. 
    i = 0 
    while i < n - 2: 
     num = nums[i] 

     left = i + 1 
     right = n - 1 

     # O(1/2k) where k is n-i? Not 100% sure about this one 
     while left < right: 
      # I think its worth the memory alloc for the vars to not have to hit the list index twice. Not sure 
      # how much faster it really is. Might save two lookups per cycle. 
      left_num = nums[left] 
      right_num = nums[right] 
      s = num + left_num + right_num # check if current sum is 0 
      if s == 0: 
       # add to the solution set only if this triplet is unique 
       # Hash lookup 
       solutions.add(tuple([right_num, num, left_num])) 
       right -= 1 
       left += 1 
      elif s > 0: 
       right -= 1 
      else: 
       left += 1 
     i += 1 

    return list(solutions)