“超过时间限制”； LeetCode的三和问题？ [英] "Time Limit Exceeded" on LeetCode's three-sum problem?

问题描述

我正在尝试解决LeetCode上的

类似地，此解决方案

 从itertools i mport组合
 
类解决方案：
 def threeSum（self，nums）：
 
：type nums：List [int] 
：rtype ：List [List [int]] 
 
 _map = self.get_map（nums）
 
结果= set（）
用于组合i，j （range（len（nums）），2）：
 target = -nums [i]-nums [j] 
如果目标在_map和_map [target]和_map [target]中-set（[ i，j]）：
 results.add（tuple（sorted（[target，nums [i]，nums [j]]））））
 return [列出结果的列表（结果）] 
 
 @staticmethod 
 def get_map（nums）：
 _map = {} 
用于索引，num枚举（nums）：
如果_map中的num： 
 _map [num] .add（index）
 else：
 _map [num] = set（[index]）
 return _map 
  

对于包含一长串零的输入，会产生超出时间限制：

此问题以前已经问过（

解决方案

这对我有用，对许多重复元素使用了一些优化。我们存储每个元素的外观计数，然后仅迭代每个不同的元素。其余操作与您已经完成的操作类似

 从集合import计数器
导入itertools 
 
类解决方案：
 def threeSum（self，nums）：
 counts =计数器（nums）
 numSet = list（set（nums））
 result = set（）
 
用于idx，枚举（numSet）中的num1：
用于idx2，枚举中的num2（itertools.islice（numSet，idx，None），start = idx）：
 num3 = （num1 + num2）* -1 
如果num3计数：
d =计数器（[num1，num2，num3]）
如果不存在任何数字（d [n]> counts [n]对于d中的n）：
 result.add（tuple（sorted（[num1，num2，num3]）））
 
返回列表（结果）
  

I'm trying to solve the three-sum problem on LeetCode and I believe I've come up with some O(n^2) submissions, but I keep on getting a "Time Limit Exceeded" error.

For example, this solution using 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])]

Results in the following error:

Similarly, this solution,

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 

yields a "Time Limit Exceeded" for an input consisting of a long array of zeros:

This question has been asked before (Optimizing solution to Three Sum), but I'm looking for suggestions pertaining to these solutions specifically. Any idea what is making the solutions 'too slow' for LeetCode?

Update

It occurred to me that determined _map[target] - set([i, j]) - that is, whether the current set of indices are not also indices of the target value - could be expensive, so I should first look up whether the corresponding number pair has been seen or not. So I tried this:

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

However, this fails on another test case with large input numbers:

解决方案

This has worked for me, uses a few optimizations for a lot of repeated elements. We store the count of the appearances of each element and then only iterate over each different element. The rest is similar to what you have already done

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)   

这篇关于“超过时间限制”； LeetCode的三和问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！