Я считаю, что нет способа сделать это, если бы не использовалось хотя бы O (n) памяти, где n - это число элементов, которые появляются перед первой парой, которая суммирует с k.Я предполагаю, что мы используем машину с оперативной памятью, но не машину, которая допускает ужасную побитовую хакерскую работу (другими словами, мы не можем делать ничего сложного с упаковкой битов.)
Эскиз доказательства выглядит следующим образом,Предположим, что мы не храним все n элементов, которые появляются перед первой парой, которая суммируется с k.Затем, когда мы видим n-й элемент, который суммирует с некоторым предыдущим значением, чтобы получить k, есть вероятность, что мы отбросим предыдущий элемент, с которым он соединяется, и, таким образом, не будем знать, что сумма k была достигнута.Более формально, предположим, что злоумышленник мог наблюдать, какие значения мы храним в памяти, когда мы смотрели на первые n - 1 элементов и отмечали, что мы не сохранили некоторый элемент x.Тогда злоумышленник может установить следующий элемент потока равным k - x, и мы неверно сообщим, что сумма еще не достигнута, поскольку мы не помним, чтобы увидеть x.
Учитывая, что нам нужнохранить все элементы, которые мы видели, не зная больше о числах в потоке, очень хорошим подходом было бы использовать хеш-таблицу, которая содержит все элементы, которые мы видели до сих пор.При наличии хорошей хеш-таблицы на это потребуется ожидаемое количество O (n) памяти и время O (n).
Я не уверен, существует ли более умная стратегия для решения этой проблемы, если вы сделаете более сильные предположенияо видах чисел в потоке, но я довольно уверен, что это асимптотически идеально с точки зрения времени и пространства.
Надеюсь, это поможет!