Как найти пару значений для данного значения с помощью lopps?

Question

Я пытаюсь написать функцию, которая получает список чисел и целое число и возвращает кортеж, содержащий пару чисел из списка, сумма которых должна быть ближайшей к числу, полученному функцией. например: closest ([10,22,28,29,30,40], 54) -> (22,30) Для меня важно сделать это в l oop и во временной сложности O (n ). Проблема с моим кодом состоит в том, что l oop не хочет перезапускать конец списка для любого значения, которое я беру с начала списка ... Я был бы признателен за помощь :) Спасибо за помощников!

def closest(lst, x):
    max_num = 0
    cur = lst[0]
    final = 0
    my_tup = ()
    for num in lst[::-1]:
        max_num = cur + num
        if max_num <= x:
            if max_num > final:
                final = max_num
                my_tup = (cur, num)
            else:
                cur = lst[1]

    return my_tup

print(closest([10,22,28,29,30,40], 54))  ---> return: (22,29)

Answer 1

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

10,22,28,29,30,40

Это означает, что вы можете воспользоваться этой информацией, чтобы найти нужную пару в одном просмотре списка. Интуиция заключается в том, что если вам нужно большее число, вы можете go в конце списка. Решения такого типа называются техникой с двумя указателями

Проблема, которую вы пытаетесь решить, является вариантом проблемы 2SUM . В Интернете есть решения, такие как здесь

Однако я бы посоветовал вам прочитать первые пару ссылок и попытаться решить их самостоятельно.

Answer 2

С помощью модуля itertools и словаря, где ключи - это суммы пар, а значения - списки пар:

from itertools import combinations


def closest(lst, val):
    d = {}
    for element in combinations(lst, 2):
        elem_sum = sum(element)
        try:
            d[elem_sum].append(element)
        except KeyError:
            d[elem_sum] = [element]
    return d[min(d, key=lambda x: abs(x-val))]


>>> closest([10, 22, 28, 29, 30, 40], 54)
[(22, 30)]

Answer 3

Поскольку вам требуются кортежи ровно из 2 элементов, это можно сделать с помощью numpy, чтобы найти пару точек, ближайших к x. Сделайте внешнее сложение списка с собой, найдите ближайшее абсолютное расстояние до x.

import numpy as np

def closest(lst, x):
    arr = np.array(lst)
    mat = np.abs(x - (arr[:, None] + arr)).astype(float)
    mat[np.diag_indices_from(mat)] = np.NaN # Exclude tuples of same point with itself 
    i,j = np.unravel_index(np.nanargmin(mat), mat.shape)

    return arr[i], arr[j]

closest([10,22,28,29,30,40], 54)
(22, 30)

closest([10,27,28,29,30,40], 54)
(27, 28)

Answer 4

Если ваш список отсортирован, а элементы уникальны, вы можете использовать это. В противном случае я считаю, что вы можете реализовать некоторые условия в словаре и получить нужные значения.

my_dict = {i+j:(i,j) for i in mylist for j in mylist if i != j and i + j < bound} my_dict[max(t)]