我的3sum problem的leetcode算法无法通过311th test case-超过了时间限制(列表长度为3000)
嵌套循环似乎是我算法中效率最低的部分。有没有一种方法可以通过使用其他方法来提高效率?
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
for i, e in enumerate(nums):
for i2, e2 in enumerate(nums[i+1:]):
e3 = -1 * (e + e2)
l = [e,e2,e3]
l.sort()
if l in result:
continue
nums[i] = ''
nums[i2+i+1] = ''
if e3 in nums:
result.append(l)
nums[i] = e
nums[i2+i+1] = e2
return result
我也尝试删除l.sort(),但仍超过了时间限制:
nums.sort()
for i, e in enumerate(nums):
for i2, e2 in enumerate(nums[i+1:]):
e3 = -1 * (e + e2)
l = []
if e3 > e2:
l = [e,e2,e3]
elif e3 < e:
l = [e3,e,e2]
else:
l = [e,e3,e2]
if l in result:
continue
nums[i] = ''
nums[i2+i+1] = ''
if e3 in nums:
result.append(l)
nums[i] = e
nums[i2+i+1] = e2
return result
首先,一个基本规则是永远不要更改要迭代的列表。