推荐学习书目 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
这是一个创建于 2718 天前的主题，其中的信息可能已经有所发展或是发生改变。
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)的。 |
 | &nbp; 3 20015jjw 2018-06-22 02:43:52 +08:00 via Android 建议 lz 搞清楚基本数据结构再写 |
Select Language