Дано целое положительное число "target". Также дана последовательность из целых положительных чисел. Необходимо записать в выходной файл "1", если

Question

Условие задачи: дано целое положительное число "target". Также дана последовательность из целых положительных чисел. Необходимо записать в выходной файл "1", если в последовательности есть два числа, сумма которых равна значению "target" или "0", если таких нет. Число "target" и последовательность берутся из файла "input.txt". Моё решение ниже.

with open('input.txt', 'r') as input_file:
target, sequence = [x for x in input_file.read().split('\n')]
amounts = [[int(x) + int(y) for y in sequence.split()] for x in sequence.split()]
with open('output.txt', 'w') as output_file:
    for item in amounts:
        if int(target) in item:
            output_file.write('1')
            break
        else:
            output_file.write('0')
            break

Пример входных данных в файле "input.txt":
5
1 7 3 4 7 9
Вопрос: можно ли решить эту задачу другим способом, или максимально оптимизировать моё решение (хотелось бы увидеть код)? Заранее, благодарю.

Answer 1

# Если обернуть код в функцию, то можно выходить из нескольких
# вложенных циклов с помощью return
def find_target(in_file):
    target, sequence = in_file.read().splitlines()
    # Преобразуем данные в нужный тип заранее - не стоит делать этого в цикле
    target = int(target)
    sequence = list(map(int, sequence.split()))

    # На каждой итерации берём число 'a'
    for idx, a in enumerate(sequence):
        # и по очереди складываем его с каждым числом находящимся правее.
        # Числа находящиеся левее уже проверены в предыдущих итерациях
        for b in sequence[idx + 1:]:
            if target == (a + b):
                return 1
    return 0

# Открываем сразу два файла
with open("input.txt") as in_file, open("output.txt", 'w') as out_file:
    # Использую функцию print(), так как она печатает в файл с переводом строки 
    print(find_target(in_file), file=out_file)

input.txt

15
4 5 6 7 8 9 10 11 12

Answer 2

Можно решить за O(n).

Создаем словарь с количеством вхождений каждого числа за O(n). Проходимся по всем элементам словаря и проверяем есть ли в словаре элемент target - текущий элемент. Если есть, то надо проверить, что это не тот же самый элемент, если тот же самый, то он нам подходит, только, если встречается более одного раза.

Проверка это O(1), проход по всем элементам словаря это O(n).
По итогу имеем O(n) + O(n) => O(n).

from collections import Counter

your_data = [5, 4, 3, 2, 5, 6]
target = 10

data_counter = Counter(your_data)

for i in data_counter:
    if target - i in data_counter and (i != target - i or data_counter[target - i] > 1):
        print (i, target - i)
        break

Пример

Answer 3

target = int(input())
b = [int(i) for i in str(input()).split()]
b.sort()
first = 0
last = len(b) - 1
c = 0
while first < last:
    s = b[first] + b[last]
    if s == target:
        print(1)
        c = 1
        break
    else:
        if s < target:
            first += 1
        else:
            last -= 1
if c == 0:
    print(0)

БЛОГ НА HUSL

Дано целое положительное число "target". Также дана последовательность из целых положительных чисел. Необходимо записать в выходной файл "1", если

Ответы (3 шт):