我正在尝试通过使用 For 循环而不是最坏时间和 space 复杂性来解决 python 中的三数和我想使用它来更好地理解

Question

示例输入数组 = [12、3、1、2、-6、5、-8、6] 目标总和 = 0

示例输出 [[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]

我的代码如下：


def threeNumberSum(array, targetSum):

    array.sort()    
    for i in range(len(array) - 2):
        nums = []
        firstNum = array[i]
        for j in range(i + 1, len(array) - 1):
            secondNum = array[j]
            for k in range(j + 1, len(array)):
                thirdNum = array[k]
                potentialTarget = firstNum + secondNum + thirdNum
                if potentialTarget == targetSum:
                    nums.append(firstNum)
                    nums.append(secondNum)
                    nums.append(thirdNum)
                    return [[firstNum, secondNum, thirdNum]]
                
    return []

请建议我应该怎么想。谢谢

Answer 1

我认为你应该把结果放在一个列表中，否则你会在找到所有可能性之前结束函数

def threeNumberSum(array, targetSum):
    array.sort()
    possibilities = []
    for i in range(len(array) - 2): 
        firstNum = array[i]
        for j in range(i + 1, len(array) - 1):
            secondNum = array[j]
            for k in range(j + 1, len(array)):
                thirdNum = array[k]
                potentialTarget = firstNum + secondNum + thirdNum
                if potentialTarget == targetSum: 
                    possibilities.append([firstNum, secondNum, thirdNum])
    return possibilities

array = [12, 3, 1, 2, -6, 5, -8, 6]
targetSum = 0
print(threeNumberSum(array,targetSum))

回答

[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]

Answer 2

您当前的算法是 O(n^3)。您可以通过遍历所有 2 组合并使用 O(1) 哈希查找找到第三个而不是进行另一次 O(n) 迭代，将其降低到 O(n^2)：

def three_num_sum(nums, target):
    d = {n: i for i, n in enumerate(nums)}
    res = []
    for i, x in enumerate(nums[:-2]):
        for j, y in enumerate(nums[i+1:-1], i+1):
            z = target - x - y
            if d.get(z, 0) > j:
                res.append([x, y, z])
    return res

print(three_num_sum([12, 3, 1, 2, -6, 5, -8, 6], 0))
# [[-8, 2, 6], [-8, 3, 5], [1, -6, 5]]

Answer 3

你可以使用 itertools :

import itertools

arr = [12, 3, 1, 2, -6, 5, -8, 6]

def threeNumberSum(array, target_sum):
    return [perm for perm in itertools.combinations(arr, 3)  # you can change the perm number if you want another number combination length.
            if sum(perm) == target_sum]


# test
arr = [12, 3, 1, 2, -6, 5, -8, 6]
print(threeNumberSum(arr, target_sum=0))

输出：

[(3, 5, -8), (1, -6, 5), (2, -8, 6)]

我正在尝试通过使用 For 循环而不是最坏时间和 space 复杂性来解决 python 中的三数和我想使用它来更好地理解

I'm trying to solve Three Number Sum in python by using For loop instead of worst time & space complexity I want to use for better understanding

python

arrays

sorting

algorithm

hash

我正在尝试通过使用 For 循环而不是最坏时间和 space 复杂性来解决 python 中的三数和 我想使用它来更好地理解

I'm trying to solve Three Number Sum in python by using For loop instead of worst time & space complexity I want to use for better understanding

python

arrays

sorting

algorithm

hash

我正在尝试通过使用 For 循环而不是最坏时间和 space 复杂性来解决 python 中的三数和我想使用它来更好地理解