3SUM к конкретному значению - PullRequest
Новая
       6

3SUM к конкретному значению

0 голосов
/ 28 июня 2018

В настоящее время у меня есть решение, но все еще примерно на 300% медленнее. Проблема состоит в том, чтобы найти подмножество из трех чисел с суммой n из заданного списка. 

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

Ответы [ 2 ]

0 голосов
/ 18 сентября 2018

Я полностью согласен с Shinobi, но если вам нужно быстро рассчитать такие задачи, C ++ - это путь. Код будет выглядеть так: 

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();
        }
    }
}
0 голосов
/ 28 июня 2018

Вы индексируете свой словарь шесть раз во внутреннем цикле, что совершенно не нужно и, вероятно, составляет основную часть вашего времени работы. Вы можете сделать только с одной операцией индексации и без каких-либо изменений в словаре: 

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)

Также, как уже предлагалось в комментариях, нет смысла сортировать входные данные.

Обновление : Также из комментариев ваш внутренний цикл начинается с 1. Это примерно удваивает ваше время выполнения.

Обновление 2 : Кроме того, учитывая, что счетчик из словаря больше не нужен, словарь теперь может быть набором (хотя и не уверен, что он повлияет на производительность каким-либо значимым образом.)

Обновление 3 : добавлена ​​проверка для n != m.

...