Русские Блоги
Учитывая целочисленный массив и целое число k, вам нужно найти количество последовательных подмассивов в массиве, сумма которых равна k.
Пример 1
Описание
- Длина массива [1, 20 000].
- Диапазон элементов в массиве составляет [-1000, 1000], а диапазон целого числа k составляет [-1e7, 1e7].
Передано 25 231 отправка)
Идея первая ( O ( n 2 ) O(n^2) O ( n 2 ) ）
- Начинайте с каждого числа и накапливайте до конца.Если оно равно k, увеличивайте на единицу.
- тайм-аут.
Идея вторая ( O ( n ) O(n) O ( n ) ）
- сумма означает накопление с первого числа. Используйте хеш-таблицу ht, чтобы записать количество вхождений каждой суммы. При накоплении числа каждый раз проверяйте, есть ли сумма k в хэш-таблице. Если да, это означает, что перед числом стоит непрерывное число, а сумма равна k. В это время количество вхождений sum-k — количество раз, которое необходимо увеличить возвращаемое значение.
- Например, на рисунке ниже sum-k находится в хеш-таблице, то есть a + b + c находится в хеш-таблице, поэтому есть d + e + f = k.
- Поскольку числа в массиве положительные или отрицательные, количество раз, когда sum-k появляется в хеш-таблице, не обязательно равно 1. Например, на рисунке ниже -1 + 1 = 0, -1 + 1-1 + 1 = 0, -1 + 1-1 + 1-1 + 1 = 0, и есть 3 последовательных нуля. Итак, если мы хотим, чтобы k было 2, будет 3 последовательных подмассива.
Интеллектуальная рекомендация
Реализация JavaScript Hashtable
причина Недавно я смотрю на «Структуру данных и алгоритм — JavaScript», затем перейдите в NPMJS.ORG для поиска, я хочу найти подходящую ссылку на библиотеку и записывать его, я могу исполь.
MySQL общие операции
jdbc Транзакция: транзакция, truncate SQL заявление Transaction 100 000 хранимая процедура mysql msyql> -определить новый терминатор,Пробелов нет mysql>delimiter // mysql> -создание хранимой .
Используйте Ansible для установки и развертывания TiDB
жизненный опыт TiDB — это распределенная база данных. Настраивать и устанавливать службы на нескольких узлах по отдельности довольно сложно. Чтобы упростить работу и облегчить управление, рекомендуетс.
Последняя версия в 2019 году: использование nvm под Windows для переключения между несколькими версиями Node.js.
С использованием различных интерфейсных сред вы можете переключаться между разными версиями в любое время для разработки. Например, развитие 2018 года основано наNode.js 7x версия разработана. Тебе эт.
Шаблон проектирования — Создать тип — Заводской шаблон
Заводская модель фабрикиPattern Решать проблему: Решен вопрос, какой интерфейс использовать принципСоздайте интерфейс объекта, класс фабрики которого реализуется его подклассом, чтобы процесс создания.
По заданному входному массиву найти все подмассивы с заданной суммой K
Учитывая входной массив, мы можем найти один подмассив, который суммируется с K (данным) за линейное время, отслеживая найденную сумму и начальную позицию. Если текущая сумма становится больше, чем K, мы продолжаем удалять элементы из начальной позиции, пока не получим текущую сумму <= K.
Я нашел пример кода от geeksforgeeks и обновил его, чтобы вернуть все такие возможные наборы. Но предполагается, что входной массив состоит только из пяти чисел.
Мой вопрос: есть ли у нас такое решение и для смешанного набора чисел (как положительных, так и отрицательных чисел)?
задан 19 фев ’13, 01:02
@jogojapan, удален тег C++. Но вопрос, который вы указали, другой, для этого требуется подмассив НЕ МЕНЕЕ «k» последовательных элементов с максимальной суммой. Я прошу подмассив любой длины с заданной суммой. — user1071840
@jogojapan. Для максимальной суммы у нас есть алгоритм Кадане, который учитывает как положительные, так и отрицательные входные данные и может быть обновлен, чтобы состоять ровно из «k» элементов. — user1071840
@jogojapan. Да, я уверен, что это будет обман . но не смог найти такой опубликованный. — user1071840
@ user1071840 Конечно. Просто чтобы вы знали, я удалю свои комментарии выше, чтобы никто не нажимал кнопку «закрыть голосование» преждевременно. — jogojapan
7 ответы
Не существует алгоритма линейного времени для случая как положительных, так и отрицательных чисел.
Поскольку вам нужны все подмассивы, сумма которых равна K , временная сложность любого алгоритма не может быть лучше, чем размер результирующего набора подмассивов. И этот размер может быть квадратичным. Например, любой подмассив [K, -K, K, -K, K, -K, . ] , начинающийся и заканчивающийся положительным ‘K’, имеет требуемую сумму, и существует N 2 /8 таких подмассивов.
Тем не менее, можно получить результат за ожидаемое время O(N), если доступно O(N) дополнительного места.
Вычислите сумму префикса для каждого элемента массива и вставьте пару (prefix_sum, index) на хеш-карту, где prefix_sum это ключ и index значение, связанное с этим ключом. Поиск prefix_sum — K в этой хеш-карте, чтобы получить один или несколько индексов массива, где начинаются результирующие подмассивы:
Это не опечатка. Я доказал, что время O(N) в худшем случае невозможно. Но здесь я объясняю алгоритм ожидаемого времени O(N). — Евгений Клюев
Это действительно отличное решение. Оно находит все возможные непрерывные подряды суммы K. — Нирдеш Шарма
Я не понимаю этого алгоритма. у кого-нибудь есть рабочий код для этого? — LE
что такое стартовый список 2. Он переопределяется в каждом цикле, но на самом деле не используется. Меня это очень смущает. — временное_имя_пользователя
Я вообще не следую этому алгоритму. Я понимаю часть «построить таблицу префиксов», но на этом мое понимание заканчивается. В этой таблице указаны только суммы массивов, начиная с индекса элемента. 0 , так что хорошего? Я пытался понять псевдокод и не смог. — временное_имя_пользователя
Решение, данное @Evgeny Kluev, закодировано на Java с небольшим объяснением.
Количество подмассивов сумма которых равна заданному числу
using namespace std;
int findSubarraySum( int arr[], int n, int sum)
unordered_map< int , int > prevSum;
for ( int i = 0; i < n; i++)
if (currsum == sum)
if (prevSum.find(currsum — sum) !=
res += (prevSum[currsum — sum]);
int n = sizeof (arr) / sizeof (arr[0]);
cout << findSubarraySum(arr, n, sum);
public class GfG
static int findSubarraySum( int arr[], int n, int sum)
HashMap <Integer, Integer> prevSum = new HashMap<>();
for ( int i = 0 ; i < n; i++)
if (currsum == sum)
if (prevSum.containsKey(currsum — sum))
res += prevSum.get(currsum — sum);
Integer count = prevSum.get(currsum);
prevSum.put(currsum, count+ 1 );
public static void main(String []args)
int n = arr.length;
System.out.println(findSubarraySum(arr, n, sum));
from collections import defaultdict
def findSubarraySum(arr, n, Sum ):
prevSum = defaultdict( lambda : 0 )
for i in range ( 0 , n):
if currsum = = Sum :
if (currsum — Sum ) in prevSum:
res + = prevSum[currsum — Sum ]
if __name__ = = «__main__» :
arr = [ 10 , 2 , — 2 , — 20 , 10 ]
print (findSubarraySum(arr, n, Sum ))
public static int findSubarraySum( int [] arr,
Dictionary < int , int > prevSum = new Dictionary< int , int >();
Найти подмассивы с заданной суммой в массиве
Дан целочисленный массив, найти в нем подмассивы с заданной суммой.
Input:
Output:
Subarrays with the given sum are
Обратите внимание, что проблема конкретно нацелена подмассивы которые являются смежными (т. е. занимают последовательные позиции) и по своей сути поддерживают порядок элементов.
1. Решение грубой силы
Простое решение — рассмотреть все подмассивы и вычислить сумму их элементов. Если сумма подмассива равна заданной сумме, выведите ее. Этот подход демонстрируется ниже на C, Java и Python:
результат:
[3, 4]
[3, 4, -7, 1, 3, 3]
[1, 3, 3]
[3, 3, 1]
Python
результат:
[3, 4]
[3, 4, -7, 1, 3, 3]
[1, 3, 3]
[3, 3, 1]
Этот подход требует O(n 3 ) время, когда сумма подмассива вычисляется в O(1) время для каждого из n 2 подмассивы массива размером n , и это занимает O(n) время для печати подмассива.
2. Хеширование
Мы также можем использовать Хеширование найти подмассивы с заданной суммой в массиве с помощью карты списков или multimap для хранения конечного индекса всех подмассивов, имеющих заданную сумму. Идея состоит в том, чтобы пройти по заданному массиву и сохранить сумму элементов, просмотренных до сих пор. При любом индексе i , позволять k быть разницей между суммой элементов, увиденных до сих пор, и заданной суммой. Если ключ k присутствует на карте, хотя бы один подмассив имеет заданную сумму, заканчивающуюся текущим индексом i , и мы печатаем все такие подмассивы.
Ниже приведена реализация вышеуказанного алгоритма на C++, Java и Python: