一對夫婦的改進,你可以讓你的算法:
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)
我覺得作爲列表已經處於有序,複雜度爲O(n的內循環),即線性搜索可以被簡化爲i和n-1之間的二分搜索,然後總的時間複雜度將從O(n^2)減少到O(nlogn)。一旦我回到家,我會爲此發佈一個答案... – zenwraight
直到那時我想你可以嘗試這種方法.. – zenwraight
@zenwraight感謝您的建議。我會嘗試二進制搜索。期待你的回答。:) –