Количество подмассивов с суммой меньше или равной заданному k
Да, есть алгоритм O (n lgn), если все элементы неотрицательны.
- Определите p[i] как сумму p[0..i] (мы называем это префиксной суммой)
- Для каждого i : максимум двоичного поиска j такой, что p[j] — p[i-1] <= k , добавить j-i+1 в счетчик
Общая сложность O(n) + O(n lgn) = O(n lgn)
Это работает потому, что для каждого i мы пытаемся найти максимальный диапазон, начиная с i , так что сумма этого диапазона равна [i..j] , так как все элементы неотрицательны, поэтому [i..i], [i..i+1], [i..i+2] . [i..j] — это все подмассивы, сумма которых j-i+1 .
Мы находим такой диапазон для каждого i и продолжаем добавлять количество подмассивов, начиная с i , сумма которых 8
Как указал Шоул, если все элементы неотрицательны, вы действительно можете использовать технику «двух указателей» для решения этой проблемы за O (n).
В основном у вас есть два указателя слева и справа, оба инициализированы на 0. Вы увеличиваете правый указатель и отслеживаете текущую сумму: пока текущая сумма внутри скользящего окна k, вы увеличиваете левый указатель на единицу, чтобы уменьшить сумму внутри окна. Каждый раз, когда окно допустимо и left = i и right = j, вы можете сказать, что есть еще j-i подмассивов, которые действительны (подмассивы, начинающиеся с k [i, j] и заканчивающиеся в j), которые не учитывались ранее.
Поиск числа подмассивов, сумма которых равна 'k'
Нам будет задан массив целых чисел и значение k . Нам нужно найти общее количество подмассивов, сумма которых равна k .
Я нашел интересный код онлайн (на Leetcode), который выглядит следующим образом:
Чтобы понять это, я прошел через некоторые конкретные примеры, такие как [1,1,1,1,1] с k=3 и [1,2,3,0,3,2,6] с k=6 . Хотя код работает отлично в обоих случаях, я не понимаю, как он на самом деле вычисляет результат.
У меня есть две конкретные проблемы:
1) Почему код постоянно добавляет значения в массив без его обнуления? Например, в случае [1,1,1,1,1] с k=3 , после sum=3 , нам не нужно сбросить sum до нуля? Не переустанавливает ли sum на поиск более поздних подмассивов?
2) result++ мы не должны просто делать result++ когда находим подрамник суммы k ? Почему мы preSum.get(sum-k) этого добавляем preSum.get(sum-k) ?
Сначала разрешите первую путаницу:
Причина, по которой код продолжает суммировать массив и не сбрасывает sum заключается в том, что мы сохраняем сумму в preSum (предыдущие суммы) по мере preSum . Тогда, всякий раз, когда мы доходим до точки, где sum-k является предыдущей суммой (скажем, по индексу i ), мы знаем, что сумма между индексом i и нашим текущим индексом равна k .
Например, на изображении ниже с i=2 и нашим текущим индексом, равным 4 , мы видим, что с 9 сумма в нашем текущем индексе, минус 3 , сумма при индексе i равна 6 , сумма между индексами 2 и 4 (включительно) составляет 6 .
Другой способ подумать об этом состоит в том, чтобы увидеть, что отбрасывание [1,2] из массива (при нашем текущем индексе 4 ) дает нам подматрицу суммы 6 по тем же причинам, что и выше (см. Изображение для деталей).
Используя этот метод мышления, мы можем сказать, что хотим отказаться от фронта массива до тех пор, пока мы не останемся с подматрицей суммы k . Мы могли бы сделать это, сказав, что для каждого индекса «отбросьте только 1 , затем отбросьте 1+2 , затем отбросьте 1+2+3 и т.д. «(Эти цифры взяты из нашего примера), пока мы не найдем подматрицу суммы k ( k=6 в нашем примере).
Это дает совершенно правильное решение, но обратите внимание, что мы будем делать это при каждом индексе нашего массива и, таким образом, суммируя одинаковые числа снова и снова. Способ сохранения вычислений — сохранить эти суммы для последующего использования. Еще лучше, мы уже суммируем эти же цифры, чтобы получить нашу текущую sum , поэтому мы можем просто сохранить это общее количество, когда мы идем.
Чтобы найти подмассив, мы можем просто посмотреть через наши сохраненные суммы, вычитая их и тестирование, если то, что мы остались в k . Это немного раздражает, чтобы вычесть каждую сохраненную сумму, поэтому мы можем использовать коммутативность вычитания, чтобы увидеть, что если sum-x=k истинно, sum-k=x также верно. Таким образом, мы можем просто увидеть, является ли x сохраненной суммой, и, если это так, знаете, мы нашли подмассиво размером k . Хэш-карта делает этот поиск эффективным.
Теперь для вашего второго путаницы:
Большую часть времени вы правы, найдя подходящий подмассив, мы могли бы просто сделать result++ . Почти всегда значения в preSum будут preSum 1 , поэтому result+=preSum.get(sum-k) будет эквивалентно result+=1 или result++ .
Единственный раз, когда это не так, когда preSum.put вызывается на sum , которая была достигнута ранее. Как мы можем вернуться к sum мы уже имели? Единственный способ — либо с отрицательными числами, которые сокращают предыдущие числа, либо с нулем, что вообще не влияет на сумму.
В принципе, мы возвращаемся к предыдущей sum когда sum подмары равна 0. Два примера таких подмассивов — [2,-2] или тривиальные [0] . С таким подмассивом нам нужно добавить более 1 чтобы получить result k+2-2=k или k+0=k , и, следовательно, мы нашли более одного подмассива, один с подмассивом с нулевой суммой ( sum=k+0 ) и один без него ( sum=k ).
Количество подмассивов, имеющих сумму, точно равную k
Задав несортированный массив целых чисел, найдите количество подмассивов, имеющих сумму, точно равную заданному числу k.
Простое решение — обойти все подмассивы и рассчитать их сумму. Если сумма равна требуемой сумме, то увеличивается число подмассивов. Вывести итоговое количество подмассивов.
Эффективное решение при обходе массива — хранить сумму до сих пор в currsum. Также ведите подсчет различных значений currsum на карте. Если значение currsum равно требуемой сумме в любом случае, увеличивайте количество подмассивов на единицу. Значение currsum превышает желаемую сумму на currsum — sum. Если это значение будет удалено из курса, тогда желаемая сумма может быть получена. На карте найдите количество ранее найденных подмассивов, имеющих сумму, равную сумме currsum-sum. Исключение всех этих подмассивов из текущего подмассива, дает новые подмассивы, имеющие желаемую сумму. Так что увеличивайте количество на количество таких подмассивов. Обратите внимание, что когда currsum равен требуемой сумме, тогда также проверьте количество подмассивов, ранее имевших сумму, равную 0. Исключение этих подмассивов из текущего подмассива дает новые подмассивы, имеющие желаемую сумму. Увеличьте счет на количество подмассивов с суммой 0 в этом случае.
// C ++ программа для поиска количества подмассивов
// с суммой, точно равной k.
#include <bits/stdc++.h>
using namespace std;
// Функция для определения количества подмассивов
// с суммой, точно равной k.
int findSubarraySum( int arr[], int n, int sum)
// STL карта для хранения количества подмассивов
// начиная с нулевого индекса
// конкретное значение суммы.
unordered_map< int , int > prevSum;
// Сумма элементов на данный момент.
for ( int i = 0; i < n; i++) <
// Добавить текущий элемент к сумме пока.
// Если курс равен желаемой сумме,
// тогда найден новый подмассив. Так
// увеличить количество подмассивов.
if (currsum == sum)
// курс превышает указанную сумму на курс
// — сумма. Найти количество подмассивов, имеющих
// эту сумму и исключаем эти подмассивы
// из currsum путем увеличения счета на
// то же количество.
if (prevSum.find(currsum — sum) !=
res += (prevSum[currsum — sum]);
// Добавить значение currsum к числу
// разные значения суммы.
int n = sizeof (arr) / sizeof (arr[0]);
cout << findSubarraySum(arr, n, sum);
// Java-программа для поиска количества подмассивов
// с суммой, точно равной k.
public class GfG<
// Функция для определения количества подмассивов
// с суммой, точно равной k.
static int findSubarraySum( int arr[], int n, int sum)
// HashMap для хранения количества подмассивов
// начиная с нулевого индекса
// конкретное значение суммы.
HashMap <Integer, Integer> prevSum = new HashMap<>();
// Сумма элементов на данный момент.
for ( int i = 0 ; i < n; i++) <
// Добавить текущий элемент к сумме пока.
// Если курс равен желаемой сумме,
// тогда найден новый подмассив. Так
// увеличить количество подмассивов.
if (currsum == sum)
// курс превышает указанную сумму на курс
// — сумма. Найти количество подмассивов, имеющих
// эту сумму и исключаем эти подмассивы
// из currsum путем увеличения счета на
// то же количество.
if (prevSum.containsKey(currsum — sum))
res += prevSum.get(currsum — sum);
// Добавить значение currsum к числу
// разные значения суммы.
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));
// Этот код предоставлен Rituraj Jain
# Python3 программа для поиска номера
# подмассивы с суммой, точно равной k.
from collections import defaultdict
# Функция для определения количества подмассивов
# с суммой, точно равной k.
def findSubarraySum(arr, n, Sum ):
# Словарь для хранения количества подмассивов
# начиная с нуля индекса, имеющего
# конкретное значение суммы.
prevSum = defaultdict( lambda : 0 )
# Сумма элементов до сих пор.
for i in range ( 0 , n):
# Добавить текущий элемент к сумме пока.
# Если курс равен желаемой сумме,
# тогда найден новый подмассив. Так
# увеличить количество подмассивов.
if currsum = = Sum :
# currsum превышает данную сумму на currsum — сумму.
# Найти количество подмассивов, имеющих
# эту сумму и исключить эти подмассивы
# от currsum путем увеличения счета на
# то же количество.
if (currsum — Sum ) in prevSum:
res + = prevSum[currsum — Sum ]
# Добавить значение currsum к числу
# разные значения суммы.
if __name__ = = «__main__» :
arr = [ 10 , 2 , — 2 , — 20 , 10 ]
print (findSubarraySum(arr, n, Sum ))
# Этот код предоставлен Rituraj Jain
// C # программа для поиска количества подмассивов
// с суммой, точно равной k.
// Функция для определения количества подмассивов
// с суммой, точно равной k.
public static int findSubarraySum( int [] arr,
// HashMap для хранения количества подмассивов
// начиная с нулевого индекса
// конкретное значение суммы.
Dictionary < int , int > prevSum = new Dictionary< int , int >();
// Сумма элементов на данный момент
for ( int i = 0; i < n; i++)
// Добавить текущий элемент к сумме пока.
// Если курс равен желаемой сумме,
// тогда найден новый подмассив. Так
// увеличить количество подмассивов.
if (currsum == sum)
// курс превышает указанную сумму на курс
// — сумма. Найти количество подмассивов, имеющих
// эту сумму и исключаем эти подмассивы
// из currsum путем увеличения счета на
// то же количество.
if (prevSum.ContainsKey(currsum — sum))
res += prevSum[currsum — sum];
// Добавить значение currsum к числу
// разные значения суммы.
int count = prevSum[currsum];
prevSum[currsum] = count + 1;
public static void Main()
int n = arr.Length;
Console.Write(findSubarraySum(arr, n, sum));
// Этот код предоставлен
// sanjeev2552
Сложность времени: O (n)
Вспомогательное пространство: O (n)