最有效的3sum算法使用python的leetcode挑战

ebdffaop  于 2023-05-21  发布在  Python
关注(0)|答案(4)|浏览(136)

我无法通过使用Python的3sum问题的leetcode时间限制测试。有人能做到吗?谢谢!
我的现有代码:

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

        solution=[]

        for i in range(len(nums)):
            tmp={}
            for j in range(1+i,len(nums)):
                if -(nums[j]+nums[i]) in tmp:
                    solution.append(tuple(sorted((nums[j],nums[i],-(nums[j]+nums[i])))))
                else:
                    tmp[nums[j]]=j

        return list(set(solution))
b5lpy0ml

b5lpy0ml1#

不知道你的解决方案有什么问题。我认为诀窍是将结果对象视为multisets,在python中称为collections.Counter。我们也可以使用itertools.combinations来完成从输入中获取所有3的组合。

import itertools
import collections

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

        res = []
        for t in itertools.combinations(nums, 3):
            if sum(t) == 0:
                c = collections.Counter(t)
                if c not in res:
                    res.append(c)
        return [list(t.elements()) for t in res]

测试:

Solution().threeSum([-1, 0, 1, 2, -1, -4])
# --> [[-1, 0, 1], [-1, -1, 2]]
t40tm48m

t40tm48m2#

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
    
        items = len(nums)
        nums.sort()
        outputs = set()
        i = 0
        while i < items-2:
            if i > 0 and nums[i] == nums[i-1]: 
                i += 1
                continue
            j = i+1
            k = items-1
            
            while j<k:
                sums = nums[j] + nums[i] + nums[k]
                if sums == 0: 
                    if (nums[i], nums[j], nums[k]) not in outputs:
                        outputs.add((nums[i], nums[j], nums[k]))
                        while j < k and nums[j] == nums[j+1]: j+=1
                        while k > j and nums[k] == nums[k-1]: k-=1
                    j += 1
                    k -= 1
                elif sums < 0: 
                    j+= 1
                    #while j < k and nums[j] == nums[j-1]: j+=1
                else:
                    k -= 1
                    #while k > j and nums[k] == nums[k+1]: k-=1

            i += 1
            
        return outputs
mwg9r5ms

mwg9r5ms3#

我的解决方案有点不同:

nums = [-1,0,1,2,-1,-4]
mysum = 0
def threeSum(nums, mysum):
    data = nums
    result = []
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            kdata = list(data)

            if j <= (len(data)):
                mys = (mysum - (data[i] + data[j]))
                datai = data[i] 
                dataj = data[j]
                kdata.pop(i)
                kdata.pop(j - 1)
                if mys in kdata:
                    ss = [mys, datai, dataj]
                    ss.sort()
                    if ss not in result:
                        result.append(ss)

        
    print(result)
threeSum(nums, mysum)

结果:

[[-1, 0, 1], [-1, -1, 2]]
gkl3eglg

gkl3eglg4#

也许不是最有效的方法,但它很简单。

arr = [1,2,3,4,5,6]
val = 9

class ThreeSum:
    def solve(self, arr, val):
        res = []
        for i, v1 in enumerate(arr):
            for j, v2 in enumerate(arr):
                for k, v3 in enumerate(arr):
                    if i != j  != k != i:
                        if v1+v2+v3 == val:
                            res.append([v1, v2, v3])
        return res

print(ThreeSum().solve(arr, val))
# (1, 2, 6)

很高兴它有帮助!如果有任何疑问请评论。

相关问题