3Sum solution by dynamic programing in Python


  • 0
    S

    ...

    compose the 2-elements list

    def BuildList2(inList1, idx2):
    inList2 = []
    for ele1 in inList1:
    inList2.append([ele1, idx2])
    return inList2

    2sum solution by dynamic programing

    def Sum2(inList, targetValue):
    # a + b = sum
    n = len(inList)
    outList2 = []
    # Sum2(n) = Sum2(n-1, sum - inList[n-1]) + Sum2(n-1, sum)
    if (n > 2):
    lastValue = inList[n-1]
    findValue = targetValue - lastValue
    inList1 = []
    try:
    inList1.append(inList.index(findValue, 0, n-1))
    except:
    # continue
    pass
    outList2 = BuildList2(inList1, n-1) + Sum2(inList[:n-1], targetValue)
    else: # if n == 2
    if targetValue == sum(inList) :
    return [[0, 1]]
    return outList2

    compose the 3-elements list

    def BuildList3(inList2, idx3):
    inList3 = []
    for ele2 in inList2:
    inList3.append([ele2[0], ele2[1], idx3])
    return inList3

    3sum solution by dynamic programing, based on 2sum solution

    def Sum3(inList, targetValue):
    # a + b + c = sum
    n = len(inList)
    outList3 = []
    # Sum3(n) = Sum3(n-1, sum - inList[n-1]) + Sum3(n-1, sum)
    if (n > 3):
    outList2 = Sum2(inList[0:n-1], targetValue - inList[n-1])
    outList3 = BuildList3(outList2, n-1) + Sum3(inList[0:n-1], targetValue)
    else: # if n == 3
    if targetValue == sum(inList) :
    return [[0, 1, 2]]
    return outList3

    in3 = [3, 5, 2, 1, 6, 7, 9, 8, -1, 4]
    outList = Sum3(in3, 12)
    print(outList)
    ...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.