LeetCode 四数之和算法题优化( Python )

2018-06-21 18:18:37 +08:00
 ChenJHua

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]
2773 次点击
所在节点    Python
3 条回复
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)]
>>>
twistoy
2018-06-21 23:20:12 +08:00
dicti.keys()返回的是一个 list,判断一个元素是不是在一个 list 里是 O(n)的。这里直接 if exp in dicti 就可以了,判断一个元素是不是在一个 dict 里是 O(1)的。
20015jjw
2018-06-22 02:43:52 +08:00
建议 lz 搞清楚基本数据结构再写

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/464801

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX