用LeetCode求解LeetCode 3和问题

Question

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

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]

使用以下测试套件：

def set_equals(a, b):
    # Auxiliary method for testing
    return set(tuple(x) for x in a) == set(tuple(y) for y in b)


def test_unique():
    assert Solution().threeSum([0, 0]) == []


def test_1():
    nums = [-1, 0, 1, 2, -1, 4]
    assert set_equals(
        Solution().threeSum(nums),
        [
          [-1, 0, 1],
          [-1, -1, 2]
        ])


def test_with_duplicates():
    nums = [-1, 0, -1, 0, 1]
    assert set_equals(
        Solution().threeSum(nums),
        [[-1, 0, 1]])


def test_same_number():
    assert Solution().threeSum([0, 0, 0]) == [[0, 0, 0]]


def test_3():
    assert set_equals(Solution().threeSum(
        [-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6]),
        [
            [-4, -2, 6],
            [-4, 0, 4],
            [-4, 1, 3],
            [-4, 2, 2],
            [-2, -2, 4],
            [-2, 0, 2]])


def test_4():
    assert set_equals(Solution().threeSum(
        [-4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0]),
        [
            [-5, 1, 4],
            [-4, 0, 4],
            [-4, 1, 3],
            [-2, -2, 4],
            [-2, 1, 1],
            [0, 0, 0]])


def test_6():
    assert set_equals(
        Solution().threeSum([0, 3, 0, 1, 1, -1, -5, -5, 3, -3, -3, 0]),
        [[-3, 0, 3], [-1, 0, 1], [0, 0, 0]])

所有测试都在本地通过：

$ 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相同的测试用例！

实际上，如果我在ipython shell中运行此输入(在将文件重命名为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

我对正在发生的事情做了许多测试。

这与字典项键、值对并不是按被推入字典的顺序相同的事实有关。

例如，您的字典可能有d = {1:'a', 2:'b', 3:'c'}，但是在迭代字典时：

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

我们不能保证你能得到这样的指纹：

1, 'a'
2, 'b'
3, 'c'

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

至于它为什么在您的机器(甚至我的机器)中工作，是因为我可以冒昧地猜测，我们有Python (我肯定会)，其中保留了字典的输入顺序。

Leetcode运行Python3，而不是3.5+。

所以当你在查字典的时候

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

根据doublet, indices出现的顺序(不能保证IT将以任何特定的顺序出现)，您不能保证循环执行是相同的！

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

我不是OrderedDict的专家，所以我无能为力。

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

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

无论是在您自己的本地机器中还是在您的Leetcode输出中，都将向您展示我的意思。打印doublet, indices使它们在您的Leetcode输出和本地机器输出中以不同的顺序显示。

Answer 2

问题的核心是break语句，它引入了阿菲舍克解释的“订单依赖”。如果我注释掉break语句，我会得到一个不同的错误，Time Limit Exceeded

​

​

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