python – 优化三和的解决方案
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 优化三和的解决方案，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3555字，纯文字阅读大概需要6分钟。
内容图文
我试图解决3 Sum问题：
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.
以下是我对此问题的解决方案：
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读过这个讨论.这对我没有帮助解决这个问题.
解决方法:
您可以对算法进行一些改进：
1)使用sets而不是列表作为您的解决方案.使用集合将确保您没有任何重复,并且您不必在解决方案中执行if new_solution：check.
2)为全零列表添加边缘案例检查.没有太多开销,但在某些情况下节省了大量时间.
3)将枚举更改为秒.它快一点.奇怪的是,我在测试中使用while循环获得了更好的性能,然后是n_max = n -2;对于范围内的i(0,n_max)：读取x范围或范围的this问答应该更快.
注意：如果我运行测试5次,我将无法获得相同的时间.我所有的测试都是-100毫秒.因此,需要进行一些小的优化.对于所有python程序,它们可能不会更快.对于运行测试的确切硬件/软件配置,它们可能更快.
另外：如果你删除了代码中的所有注释,那么速度快了300毫安的HAHAHAH.只是一个有趣的副作用然而测试正在运行.
我已将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).它还暗示了一种使算法速度更快的方法(使用更多设置;))
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)
内容总结
以上是互联网集市为您收集整理的python – 优化三和的解决方案全部内容，希望文章能够帮你解决python – 优化三和的解决方案所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。