I'm trying to solve Three Number Sum in python by using For loop instead of worst time & space-CodePudding

sample input array = [12, 3, 1, 2, -6, 5, -8, 6] targetSum = 0

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

my code is as follows:


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 []

Kindly suggest me how should I think. Thanks

CodePudding user response：

Your current algorithm is O(n^3). You could get it down to O(n^2) by iterating over all the 2-combinations, and using a O(1) hash lookup to find the third instead of doing another O(n) iteration:

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]]

CodePudding user response：

I think you should place result in a list otherwise you will end the function before finding all possibilities

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))

answer

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

CodePudding user response：

you can use 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))

output:

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

CodePudding user response：

you could use comments to improve maintainability of the code/

good luck.