https://leetcode-cn.com/problems/4sum/description/
我的代码,提交解答的时候通不过,显示超出时间限制,请大佬帮我优化一下:
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
res, dicti = set(), {}
numLen = len(nums)
nums.sort()
for i in range(numLen):
for j in range(i+1, numLen):
key = nums[i] + nums[j]
if key not in dicti.keys():
dicti[key] = [(i,j)]
else:
dicti[key].append((i,j))
for i in range(numLen):
for j in range(i+1, numLen-2):
exp = target - nums[i] -nums[j]
if exp in dicti.keys():
for tmpIndex in dicti[exp]:
if tmpIndex[0] > j:
res.add((nums[i], nums[j], nums[tmpIndex[0]], nums[tmpIndex[1]]))
return [list(i) for i in res]
1
xpresslink 2018-06-21 22:27:41 +08:00
>>> nums = [1, 0, -1, 0, -2, 2]
>>> target = 0 >>> from itertools import combinations as cb >>> [c for c in cb(nums, 4) if sum(c)==target] [(1, 0, -1, 0), (1, -1, -2, 2), (0, 0, -2, 2)] >>> |
2
twistoy 2018-06-21 23:20:12 +08:00
dicti.keys()返回的是一个 list,判断一个元素是不是在一个 list 里是 O(n)的。这里直接 if exp in dicti 就可以了,判断一个元素是不是在一个 dict 里是 O(1)的。
|
3
20015jjw 2018-06-22 02:43:52 +08:00 via Android
建议 lz 搞清楚基本数据结构再写
|