V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
ChenJHua
V2EX  ›  Python

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

  •  
  •   ChenJHua · 2018-06-21 18:18:37 +08:00 · 2759 次点击
    这是一个创建于 2332 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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]
    
    xpresslink
        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)]
    >>>
    twistoy
        2
    twistoy  
       2018-06-21 23:20:12 +08:00
    dicti.keys()返回的是一个 list,判断一个元素是不是在一个 list 里是 O(n)的。这里直接 if exp in dicti 就可以了,判断一个元素是不是在一个 dict 里是 O(1)的。
    20015jjw
        3
    20015jjw  
       2018-06-22 02:43:52 +08:00 via Android
    建议 lz 搞清楚基本数据结构再写
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1640 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 16:54 · PVG 00:54 · LAX 08:54 · JFK 11:54
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.