python - "Time Limit Exceeded"关于 LeetCode 的三和题？

Question

我正在尝试解决 three-sum problem on LeetCode我相信我已经提交了一些 O(n^2) 次提交，但我一直收到“超出时间限制”错误。

例如，这个解决方案使用itertools.combinations:

from itertools import combinations

class Solution:
    def threeSum(self, nums):
        results = [triplet for triplet in combinations(nums, 3) if sum(triplet) == 0]
        return [list(result) for result in set([tuple(sorted(res)) for res in results])]

导致以下错误:

同样，这个解决方案，

from itertools import combinations

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        _map = self.get_map(nums)

        results = set()
        for i, j in combinations(range(len(nums)), 2):
            target = -nums[i] - nums[j]
            if target in _map and _map[target] and _map[target] - set([i, j]):
                results.add(tuple(sorted([target, nums[i], nums[j]])))
        return [list(result) for result in results]

    @staticmethod
    def get_map(nums):
        _map = {}
        for index, num in enumerate(nums):
            if num in _map:
                _map[num].add(index)
            else:
                _map[num] = set([index])
        return _map 

对于由一长串零组成的输入产生“超出时间限制”:

此问题之前已被问到 ( Optimizing solution to Three Sum )，但我正在寻找专门针对这些解决方案的建议。知道是什么让 LeetCode 的解决方案“太慢”了吗？

更新

我突然想到确定 _map[target] - set([i, j]) - 也就是说，当前索引集是否也不是目标值的索引 - 可能是昂贵，所以我应该首先查看是否看到了相应的数字对。所以我尝试了这个:

from itertools import combinations

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        _map = self.get_map(nums)

        results = set()
        seen = set()
        for i, j in combinations(range(len(nums)), 2):
            target = -nums[i] - nums[j]
            pair = tuple(sorted([nums[i], nums[j]]))
            if target in _map and pair not in seen and _map[target] - set([i, j]):
                seen.add(pair)
                results.add(tuple(sorted([target, nums[i], nums[j]])))
        return [list(result) for result in results]

    @staticmethod
    def get_map(nums):
        _map = {}
        for index, num in enumerate(nums):
            if num in _map:
                _map[num].add(index)
            else:
                _map[num] = set([index])
        return _map

但是，这在另一个具有大量输入数字的测试用例上失败了:

Answer 1

这对我有用，对很多重复元素进行了一些优化。我们存储每个元素出现的次数，然后只迭代每个不同的元素。其余的与您已经完成的类似

from collections import Counter
import itertools

class Solution:
    def threeSum(self, nums):
        counts = Counter(nums)
        numSet = list(set(nums))
        result = set()

        for idx, num1 in enumerate(numSet):
            for idx2, num2 in enumerate(itertools.islice(numSet, idx, None), start=idx):
                num3 = (num1 + num2) * -1
                if num3 in counts:
                    d = Counter([num1, num2, num3])
                    if not any(d[n] > counts[n] for n in d):
                        result.add(tuple(sorted([num1, num2, num3])))

        return list(result)