Количество подмассивов сумма которых равна заданному числу
Перейти к содержимому

Количество подмассивов сумма которых равна заданному числу

Найти подмассив с заданной суммой в целочисленном массиве

Дан целочисленный массив, найти подмассив, содержащий заданную сумму.

Input: nums[] = , target = 15
Output:

Input: nums[] = , target = 15
Output: or

Input: nums[] = , target = -3
Output: or

1. Использование скользящего окна

Мы можем решить эту проблему с помощью раздвижное окно. Идея состоит в том, чтобы сохранить окно, которое начинается с текущего элемента, и сумма его элементов больше или равна заданной сумме. Если сумма текущего окна становится меньше заданной суммы, то окно нестабильно, и мы продолжаем добавлять элементы в текущее окно справа от него, пока окно снова не станет стабильным. Выведите окно, если его сумма равна заданной сумме в любой точке. Обратите внимание, что этот подход будет работать только с массивом положительные целые числа.

Алгоритм может быть реализован следующим образом на C++, Java и Python:

C++

// Функция для печати подмассива с заданной суммой с использованием
// метод скользящего окна
void findSubarray ( int nums [ ] , int n , int target )
// поддерживает сумму текущего окна
int windowSum = 0 ;
// поддерживаем окно [low, high-1]
int low = 0 , high = 0 ;
// рассматриваем каждый подмассив, начиная с индекса `low`
for ( low = 0 ; low < n ; low ++ ) // если сумма текущего окна меньше заданной суммы, // затем добавляем элементы в текущее окно справа while ( windowSum < target && high < n ) windowSum += nums [ high ] ; // если сумма текущего окна равна заданной сумме if ( windowSum == target ) printf ( "Subarray found [%d–%d]\n" , low , high - 1 ) ; // В этот момент сумма текущего окна больше, чем заданная сумма. // Удалить текущий элемент (крайний левый элемент) из окна windowSum -= nums [ low ] ; int main ( void ) // массив положительных целых чисел int target = 15 ; int n = sizeof ( nums ) / sizeof ( nums [ 0 ] ) ; findSubarray ( nums , n , target ) ;

результат:

Subarray found [1–3]

Java

class Main
// Функция для печати подмассива с заданной суммой с использованием
// метод скользящего окна
public static void findSubarray ( int [ ] nums , int target )
// поддерживает сумму текущего окна
int windowSum = 0 ;
// поддерживаем окно [low, high-1]
int high = 0 ;
// рассматриваем каждый подмассив, начиная с индекса `low`
for ( int low = 0 ; low < nums . length ; low ++ ) // если сумма текущего окна меньше заданной суммы, // затем добавляем элементы в текущее окно справа while ( windowSum < target && high < nums . length ) windowSum += nums [ high ] ; // если сумма текущего окна равна заданной сумме if ( windowSum == target ) System . out . printf ( "Subarray found [%d–%d]" , low , high - 1 ) ; // В этот момент сумма текущего окна больше, чем заданная сумма. // Удалить текущий элемент (крайний левый элемент) из окна windowSum -= nums [ low ] ; public static void main ( String [ ] args ) // массив положительных целых чисел int [ ] nums = < 2 , 6 , 0 , 9 , 7 , 3 , 1 , 4 , 1 , 10 >;
int target = 15 ;
findSubarray ( nums , target ) ;

результат:

Subarray found [1–3]

Python

# Функция для печати подсписка с заданной суммой с использованием
# Техника раздвижного окна 1ТП4Т
def findSublist ( nums , target ) :
# поддерживает сумму текущего окна
windowSum = 0
# поддерживает окно [low, high-1]
( low , high ) = ( 0 , 0 )
# рассматривать каждый подсписок, начиная с индекса `low`
for low in range ( len ( nums ) ) :
#, если сумма текущего окна меньше заданной суммы,
# затем добавьте элементы в текущее окно справа
while windowSum < target and high < len ( nums ) : windowSum += nums [ high ] high = high + 1 #, если сумма текущего окна равна заданной сумме if windowSum == target : print ( 'Sublist found' , ( low , high - 1 ) ) # В этот момент сумма текущего окна больше заданной суммы. # Удалить текущий элемент (крайний левый элемент) из окна windowSum -= nums [ low ] if __name__ == '__main__' : # список положительных целых чисел nums = [ 2 , 6 , 0 , 9 , 7 , 3 , 1 , 4 , 1 , 10 ] target = 15 findSublist ( nums , target )

результат:

Sublist found (1, 3)

Временная сложность приведенного выше решения равна O(n) и не требует дополнительного места, где n это размер ввода.

2. Использование хеширования

Приведенное выше решение не будет работать для отрицательных чисел. Мы можем использовать Хеширование чтобы проверить, существует ли в массиве подмассив с заданной суммой или нет. Идея состоит в том, чтобы пройти по заданному массиву и сохранить сумму элементов, просмотренных до сих пор. Если разница между текущей суммой и заданной суммой видна ранее (т. е. разница существует в наборе), вернуть true, поскольку существует по крайней мере один подмассив с данной суммой, который заканчивается на текущем индексе; в противном случае вставьте сумму в набор.

Ниже приведена реализация вышеуказанного алгоритма на C++, Java и Python:

Разработка алгоритма, обнаруживающего в массиве все пары целых чисел, сумма которых равна заданному значению.

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

Простое решение

Очень простое и эффективное (по времени) решение — создание хэш-таблицы, отображающей целое число в целое число. Данный алгоритм работает, пошагово проходя весь массив. Для каждого элемента x в хэш-таблице ищется sum – x и, если запись существует, выводится (x, sum – x). После этого x добавляется в таблицу и проверяется следующий элемент.

Альтернативное решение

Давайте начнем с формулировки. Если мы попытаемся найти пару чисел, сумма которых равна z, то дополнение будет z – x (величина, которую нужно добавить к x, что бы получить z). Если мы попытаемся найти пару чисел, при суммировании которых получается 12, дополнением к -5 будет число 17.

Представьте, что у нас есть отсортированный массив . Пусть first указывает на начало массива, а last — на его конец. Чтобы найти дополнение к first, мы двигаем last назад, пока не найдем искомую величину. Если first + last

Разбор по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»

Найти 2 элемента массива, сумма которых равна заданному числу

Дан массив целых чисел, упорядоченный строго по возрастанию. Дано некоторое число X, нужно менее чем за квадратное количество операций(то есть перебор всех пар) найти такие два любых элемента массива, что их сумма равна X, иначе вывести 0. Как сделать это меньше, чем за квадратное время?

Отслеживать
13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 22 окт 2015 в 18:11
323 1 1 золотой знак 3 3 серебряных знака 10 10 бронзовых знаков

4 ответа 4

Сортировка: Сброс на вариант по умолчанию

Решение за О(n):
Решаем методом «2 указателя»
Храним 2 индекса: первый сначала указывает на нулевой элемент, второй — на последний элемент.
Цикл — пока индексы не будут равны (то есть пока они не укажут на один и тот же элемент. Если такое случилось — значит, искомых элементов в массиве нет).
На каждой итерации цикла сравниваем текущую сумму (сумму элементов, на которые указывают индексы) с искомой. Если сумма меньше — увеличиваем первый индекс, если сумма больше — уменьшаем второй индекс. Если равна — решение найдено.

#include #include using namespace std; int main() < int *a; // массив int n; // количество элементов в массиве int sum; // необходимая сумма /// //чтение массива cin >> n; a = new int[n]; for (int i = 0; i < n; i++) cin >> a[i]; cin >> sum; /// // индексы int lt = 0; // первый, то есть левый int rt = n - 1; // второй, то есть правый while (lt != rt) < int cursum = a[lt] + a[rt]; if (cursum < sum) lt++; else if (cursum >sum) rt--; else // if (cursum == sum) < cout > cout

Отслеживать
ответ дан 22 окт 2015 в 19:41
835 1 1 золотой знак 6 6 серебряных знаков 22 22 бронзовых знака
Как такой метод найдёт все варианты пар? Хотя в задаче ОП это, вроде бы, не требуется.
22 окт 2015 в 19:52

@Sergiks не «вроде бы», а не требуется. А если потребуется — при нахождении не выходить из программы, заменить «return 0» на «rt—; lt++; «, ну то есть продолжать поиск

22 окт 2015 в 19:56
Классный вариант.
22 окт 2015 в 20:43

Поскольку массив отсортирован, то этим фактом можно воспользоваться для поиска второго элемента в паре с помощью бинарного поиска. Алгоритм следующий:

  1. Проходим массив, для каждого элемента вычисляем, какая ему нужна пара
  2. Ищем эту пару с помощью бинарного поиска
  3. Если элемент нашелся и это не текущий элемент, то мы нашли пару

Т.о. получим алгоритм со сложностью O(nlogn): цикл дает O(n), бинарный поиск дает O(logn).

bool found = false; for (int i = 0; i < array.Length; i++) < int first = array[i]; int second = X - first; // искомый элемент int index = BinarySearch(array, second); if (index >-1 && index != i) < Console.WriteLine("and ", i, index); found = true; break; > > if (!found)

Отслеживать
ответ дан 22 окт 2015 в 18:42
25.1k 4 4 золотых знака 45 45 серебряных знаков 81 81 бронзовый знак

да, согласен, но если изменить условие так: нельзя пользоваться сторонними алгоритмами; нельзя использовать коллекции или другие готовые реализации методов

22 окт 2015 в 18:52
@Lescott: Если это учебная задача, то не позорьтесь, прося нас решить её за вас.
22 окт 2015 в 20:24
Нет, это задача просто на оценку времени сложности, интересно было про разные подходы узнать)
23 окт 2015 в 3:16

  1. сосчитать необходимые дополнения до X для каждого элемента. Этой операциии не избежать. Получится убывающий ряд.
  2. двигаемся по обоим рядам от меньших к большим, пока не находится равенство. Тогда пара найдена – значение и X минус значение.

Т.о. один раз пройти, вычисляя дополнения до X, и макс. 2 раза, разыскивая совпадения. И по результатам, исключить дубли зеркальных пар, как (-3,15) в примере ниже.

Недостаток – нужно хранилище для 2 x размер данных . Это оптимизируется, но не будем усложнять.

Пример:

X = 12, исходный ряд: -3 1 3 4 7 9 12 15 -3 1 3 4 7 9 12 15 дополнения до X: 15 11 9 8 5 3 0 -3 двигаем пошагово указатель на текущий элемент в каждом ряду от меньших к большим, если бОльшее значение в одном ряду, в другом ряду берём следующее, если равны, то для след. шага сравнения берём по след. значению в обоих -3 1 3 4 7 8 12 15 -3 0 3 5 8 9 11 15 Находим -3, значит, пара (-3, 12 - -3 = 15); второе совпадение (3, 12-3=9); третье совпадение (15, 12-15=-3); 

Надо ещё пройтись по результатам и убрать зеркальные дубли пар, если есть (тут один случай).

Upd не рассмотрел случай, если дополнение = значению и повтор одинаковых значений в исходном массиве, напр. [1,3,3,4,4] .

Количество подмассивов сумма которых равна заданному числу

Вычислить значение суммы

S = 1/1! + 1/2! + . + 1/k!

Написать программу определения количества шестизначных ‘счастливых’ билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр.

Написать программу определения количества 2*N -значных билетов, у которых сумма первых N десятичных цифр равна сумме N последних десятичных цифр; при этом N -произвольное натуральное число.

Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца.

Покупатель имеет купюры достоинством A(1), . A(n), а продавец — B(1), .. ,B(m). Необходимо найти максимальную стоимость товара Р, которую покупатель не может купить, потому что нет возможности точно рассчитаться за этот товар с продавцом, хотя денег на покупку этого товара достаточно.

Задан массив М [1:N] натуральных чисел, упорядоченный по неубыванию, т.е.: M[1]

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

У покупателя есть n монет достоинством H(1). H(n). У продавца есть m монет достоинством B(1). B(l). Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима).

Задан массив М [1:N] натуральных чисел, упорядоченный по неубыванию, т.е.: M[1]

Написать алгоритм выплаты заданной суммы S минимальным количеством купюp достоинством M(1), . M(N).

По матрице A(N,N) построить матрицу B(N,N). Элемент B(I,J) равен максимальному из элементов матрицы А принадлежащем части, ограниченной справа диагоналями, проходящими через A(I,J).

Вводится матрица a(m,n) из 0 и 1. Найти в ней квадратную подматрицу из одних единиц максимального размера.

Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину).

Переформулировка задачи 11.

Фермер хочет построить на своей земле как можно больший по площади сарай. Но на его участке есть деревья и хозяйственные постройки, которые он не хочет никуда переносить. Для простоты представим ферму сеткой размера MxN. Каждое из деревьев и построек размещается в одном или нескольких узлах сетки. Прямоугольный сарай не должен ни с чем соприкасаться (т.е. в соседних с ним узлах сетки не может ничего быть).

Найти максимально возможную площадь сарая и где он может размещаться.

Дан массив A[N,M]. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным прямоугольным подмассивам.

Задана матрица натуральных чисел A(n,m). За каждый проход через клетку (i,j) взымается штраф A(i,j). Необходимо минимизировать штраф и

а) Пройти из какой-либо клетки 1-ой строки в n-ую строчку, при этом из текущей клетки можно перейти

1) в любую из 3-х соседних, стоящих в стpоке с номеpом на 1-цу большем;

2) в любую из 8 соседних клеток;

б) Реализовать пункт a) для перехода из клетки (1,1) в (n,m).

Дан выпуклый n-угольник, n=>3, своим обходом по контуру. Разбить его на треугольники (n-3)-мя диагоналями, непересекающимися кроме как по концам, таким образом чтобы

а) Cумма их длин была минимальной;

б) Максимальная из диагоналей имела наименьшую длину.

Задано число А и два вектора b[1..n] и c[1..n].

Найти множество I, являющееся подмножеством множества , такое, что

является максимальной из всех

Пусть x=(a 1 ,a 2 . a m ) и y=(b 1 ,b 2 . b n ) — две заданных строки символов.

Определим d(x,y) как минимальное число вставок, удалений и замен символа, которое необходимо для преобразования x в y.

Для заданных x и y найти d(x,y).

Вводится три неотрицательных числа d, i, c и две строки X и Y. Найти преобразование строки X в Y минимальной стоимости. Допустимы следующие три операции:

удалить любой символ из X (стоимость операции d);

вставить любой символ в X (стоимость операции i);

заменить символ в X на произвольный (стоимость операции e).

Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 — либо в непустую последовательность букв A, либо в непустую последовательность букв B?

Пусть известно, что для перемножения матрицы размера n*m на матрицу размера m*k требуется n*m*k операций. Необходимо определить, какое минимальное число операций потребуется для перемножения n матриц А 1 . А n , заданных своими размерами n(i)*m(i). При этом можно перемножать любые две рядом стоящие матрицы, в результате чего получается матрица нужного размера.

n(i) — число строк в матрице A i

m(i) — число столбцов в матрице A i

а) Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность.

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, одной пары соседних элементов ( одного «разрыва» возрастающей подпоследовательности).

Искомая подпоследовательность (1,2,3,2,3,4,6)

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, m пар соседних элементов ( возрастающая подпоследовательность с m «разрывами»).

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

Возвести число А в натуральную степень n за как можно меньшее количество умножений.

Заданы z и y — две последовательности. Можно ли получить

последовательность z вычеркиванием элементов из y.

Найти максимальную по длине последовательность z, полученную

вычеркиванием элементов как из x, так и из y.

Пусть x и y — две бинарных последовательности (т.е. элементы последовательностей — нули и единицы); x и y можно рассматривать как запись в двоичной форме некоторых двух натуральных чисел.

Найти максимальное число z, двоичную запись которого можно получить вычеркиванием цифр как из x, так и из y. Ответ выдать в виде бинарной последовательности.

Добавить комментарий

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