CODEWITHSUNDEEP
pythonalgorithmsubset-sum
Kurns
Kurns

Reputation: 157

3SUM to a specific value

I currently have a solution, but still about 300% too slow. The problem is to find a subset of three numbers with a sum n from a given list.

goal = int(input().split()[1]) #The desired sum
numbers = list(map(int, input().split())) #User-inputted numbers

myDict = {} #Created so we can quickly check if a number is present in the list

for i in numbers: #The amount of each number is stored in the dict, eg. 439797: 2
    if i in myDict:
        myDict[i] += 1
    else:
        myDict[i] = 1


numbers = sorted(numbers)


for start in range(0, len(numbers)):
    for end in range(1, len(numbers)):
        myDict[numbers[start]] -= 1 
        myDict[numbers[end]] -= 1 
        #This is done so that the same number isn't used twice
        if goal-numbers[start]-numbers[end] in myDict:
            if myDict[goal-numbers[start]-numbers[end]] > 0:
                print(goal-numbers[start]-numbers[end], numbers[start], numbers[end])
                quit()
        myDict[numbers[start]] += 1
        myDict[numbers[end]] += 1

Upvotes: 1

Views: 225

Answers (2)

Quiti
Quiti

Reputation: 132

I fully agree with shinobi, but if you need to calculate these kind of tasks quickly, C++ is the way to go. The code would look like this:

for (int i = 0, i < len(numbers); i++) {
    int m = numbers[i];
    for (int j = i + 1, j < len(numbers); j++) {
        int n = numbers[j];
        if (n != m) {
            int k = goal - m - n;
            if (k != m && k != n && myDict[k]) {
                doSomething();
        }
    }
}

Upvotes: 1

shinobi
shinobi

Reputation: 361

You're indexing your dictionary six times in the inner loop, which is completely unnecessary, and probably accounts for the bulk of your running time. You can do with just a single indexing op, and without any modifications to the dictionary:

for i in range(0, len(numbers)):
    m = numbers[i]
    for j in range(i + 1, len(numbers)):
        n = numbers[j]
        if n != m:
            k = goal - m - n
            if k != m and k != n and k in myDict:
                # accept triple (m, n, k)

Also, as already suggested in the comments, there's no point in sorting the input.

Update: Also from the comments, your inner loop starts at 1. This approximately doubles your running time.

Update 2: Also, given that the count from the dictionary is no longer needed, the dictionary can be a set now (not sure if it's going to affect performance in any meaningful way though.)

Update 3: Added check for n != m.

Upvotes: 1

Related Questions