LeetCode的三次问题* m的“超出时间限制”？-Java 学习之路

我正在尝试解决three-sum problem on LeetCode并且我相信我已经提出了一些O（n ^ 2）提交，但我继续得到"Time Limit Exceeded"错误 .

例如，此解决方案使用 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])]

导致以下错误：

enter image description here

同样，这个解决方案，

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

对于由长数组的零组成的输入，会产生“超出时间限制”：

enter image description here

之前已经问过这个问题（Optimizing solution to Three Sum），但是对于LeetCode来说我是'm looking for suggestions pertaining to these solutions specifically. Any idea what is making the solutions '太慢了？

Update

在我看来，确定 _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

但是，在具有大输入数字的另一个测试用例中，这会失败：

enter image description here

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)

回复于 2024-04-19T17:48:09+08:00

LeetCode的三次问题* m的“超出时间限制”？

1 回答

相关问题