三和优化解决方案 [英] Optimizing solution to Three Sum
问题描述
我正在尝试解决3个总和问题,表示为:
I am trying to solve the 3 Sum problem stated as:
给出n个整数的数组S,是否有元素a, b,c在S中使得a + b + c = 0?在数组中找到所有零的三元组,它们的总和为零。
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
注意:解决方案集不得包含重复的三元组。
Note: The solution set must not contain duplicate triplets.
这是我对这个问题的解决方案:
Here is my solution to this problem:
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是解数。
This solution works fine with a time complexity of O(n**2 + k)
and space complexity of O(k)
where n is the size of the input array and k is the number of solutions.
在LeetCode上运行此代码时,对于大型数组,我收到TimeOut错误。我想知道如何进一步优化我的代码以通过法官。
While running this code on LeetCode, I am getting TimeOut error for arrays of large size. I would like to know how can I further optimize my code to pass the judge.
PS:我已阅读此相关问题。这并不能帮助我解决问题。
P.S: I have read the discussion in this related question. This did not help me resolve the issue.
推荐答案
您可以对算法进行一些改进:
A couple of improvements you can make to your algorithm:
1)使用集合代替您的解决方案列表。使用集合将确保您没有任何重复项,并且如果new_solution不在解决方案中,则不必执行:
检查。
1) Use sets instead of a list for your solution. Using a set will insure that you don't have any duplicate and you don't have to do a if new_solution not in solutions:
check.
2)添加边缘情况检查以获取全零列表。不需要太多的开销,但是在某些情况下可以节省大量时间。
2) Add an edge case check for an all zero list. Not too much overhead but saves a HUGE amount of time for some cases.
3)将枚举更改为一秒钟。它快一点。奇怪的是,在使用while循环然后使用 n_max = n -2时,我在测试中获得了更好的性能。对于范围(0,n_max)中的i:
阅读
3) Change enumerate to a second while. It is a little faster. Weirdly enough I am getting better performance in the test with a while loop then a n_max = n -2; for i in range(0, n_max):
Reading this question and answer for xrange or range should be faster.
注意:如果我进行了5次测试,那么其中任何一个都不会获得相同的时间。我所有的测试都是+ -100毫秒。因此,请采取一些小的优化措施。对于所有python程序,它们可能并不真正更快。对于运行测试的确切硬件/软件配置,它们可能只会更快。
NOTE: If I run the test 5 times I won't get the same time for any of them. All my test are +-100 ms. So take some of the small optimizations with a grain of salt. They might NOT really be faster for all python programs. They might only be faster for the exact hardware/software config the tests are running on.
也可以:如果从代码中删除所有注释,则速度要快很多,例如快300毫秒。
ALSO: If you remove all the comments from the code it is a LOT faster HAHAHAH like 300ms faster. Just a funny side effect of however the tests are being run.
我已经将O()表示法放入了代码中所有需要花费大量时间的部分中。时间。
I have put in the O() notation into all of the parts of your code that take a lot of time.
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
这是一些不会超时且运行很快的代码。它还暗示了一种使算法更快的方法(使用更多设置;))
Here is some code that won't time out and is fast(ish). It also hints at a way to make the algorithm WAY faster (Use sets more ;) )
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)
这篇关于三和优化解决方案的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!