3sleeum de在Python中解决问题

Question

我正在尝试解决LeetCode上的3Sum问题。我想出了以下解决方案：

import collections


class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        d = collections.defaultdict(dict)
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                d[-nums[i]-nums[j]].update(
                    {tuple(sorted([nums[i], nums[j]])): (i, j)})

        triplets = set()
        for index, num in enumerate(nums):
            if num in d:
                for doublet, indices in d[num].items():
                    if index not in indices:
                        triplet = tuple(sorted([num, *doublet]))
                        if triplet not in triplets:
                            triplets.add(triplet)
                            break

        return [list(triplet) for triplet in triplets]

使用以下测试套件：

^{pr2}$

所有测试在本地通过：

$ pytest 3sum.py -s
============================= test session starts ==============================
platform darwin -- Python 3.6.6, pytest-3.8.1, py-1.6.0, pluggy-0.7.1
rootdir: /Users/kurtpeek/GoogleDrive/LeetCode, inifile:
collected 7 items                                                              

3sum.py .......

=========================== 7 passed in 0.04 seconds ===========================

但是，如果我在LeetCode上提交解决方案，我会得到一个“错误答案”的结果：

但是请注意，这与我的本地测试套件中的test_6是同一个测试用例！在

实际上，如果我在ipythonshell中运行此输入（在将文件重命名为threesum.py以避免导入错误之后），我将得到预期的三个结果，尽管顺序不同：

$ ipython
Python 3.6.6 (v3.6.6:4cf1f54eb7, Jun 26 2018, 19:50:54) 
Type 'copyright', 'credits' or 'license' for more information
IPython 6.5.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: from threesum import *

In [2]: Solution().threeSum([0, 3, 0, 1, 1, -1, -5, -5, 3, -3, -3, 0])
Out[2]: [[-1, 0, 1], [0, 0, 0], [-3, 0, 3]]

似乎不知何故，LeetCode的“输出”与我的输出不一样。你知道我怎样才能让解决方案被接受吗？在

Answer 1

问题的核心是break语句，它引入了由Abhishek解释的“顺序依赖关系”。如果我注释掉break语句，我会得到一个不同的错误，Time Limit Exceeded：

显然，我的O（N^2）解太慢了，但至少它现在给出了正确的答案。在

Answer 2

我对发生的事做了很多测试。在

这与字典项key、value对的出现顺序不同有关。在

例如，您的字典可能有d = {1:'a', 2:'b', 3:'c'} 但是当你在字典里重复的时候：

for key, value in d.items():
    print(key, value)

无法保证您获得此打印：

^{pr2}$

因为字典本来就应该是无序的。在

至于它为什么能在你的机器上，甚至我的机器上运行，是因为我可以大胆地猜测，我们有python3.5+（我确信），在那里，进入字典的顺序是保持不变的。在

Leetcode运行python3。不是3.5+。在

所以当你在查字典的时候

for doublet, indices in d[num].items():

根据doublet, indices出现的顺序（不能保证它会以任何特定的顺序出现），您不能保证循环的执行是相同的！在

你能做什么？我说学会使用OrderedDict。这将保留键、值对放入字典的顺序。在

我不是OrderedDict的专家，所以我帮不上忙。在

但是一个简单的印刷声明：

for doublet, indices in d[num].items():
    print(doublet, indices)

在您自己的本地机器和Leetcode输出中都会显示我的意思。。打印doublet, indices使它们以不同的顺序显示在Leetcode输出和本地机器输出中。在