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

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

  • автор:

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

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

Отслеживать
13.8k 12 12 золотых знаков 44 44 серебряных знака 77 77 бронзовых знаков
задан 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.2k 4 4 золотых знака 46 46 серебряных знаков 82 82 бронзовых знака

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

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] .

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

На входе массив чисел, например: arr = [1, -2, 3, 4, -9, 6] .

Задача: найти непрерывный подмассив в arr , сумма элементов в котором максимальна.

Функция getMaxSubSum(arr) должна возвращать эту сумму.

getMaxSubSum([-1, 2, 3, -9]) == 5 (сумма выделенных элементов) getMaxSubSum([2, -1, 2, 3, -9]) == 6 getMaxSubSum([-1, 2, 3, -9, 11]) == 11 getMaxSubSum([-2, -1, 1, 2]) == 3 getMaxSubSum([100, -9, 2, -3, 5]) == 100 getMaxSubSum([1, 2, 3]) == 6 (берём все)

Если все элементы отрицательные – ничего не берём(подмассив пустой) и сумма равна «0»:

getMaxSubSum([-1, -2, -3]) = 0

Попробуйте придумать быстрое решение: O(n 2 ), а лучше за О(n) операций.

Медленное решение

Медленное решение

Можно посчитать все возможные подсуммы.

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

Например, для [-1, 2, 3, -9, 11] :

// Начиная с -1: -1 -1 + 2 -1 + 2 + 3 -1 + 2 + 3 + (-9) -1 + 2 + 3 + (-9) + 11 // Начиная с 2: 2 2 + 3 2 + 3 + (-9) 2 + 3 + (-9) + 11 // Начиная с 3: 3 3 + (-9) 3 + (-9) + 11 // Начиная с -9 -9 -9 + 11 // Начиная с 11 11

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

function getMaxSubSum(arr) < let maxSum = 0; // если элементов не будет - возвращаем 0 for (let i = 0; i < arr.length; i++) < let sumFixedStart = 0; for (let j = i; j < arr.length; j++) < sumFixedStart += arr[j]; maxSum = Math.max(maxSum, sumFixedStart); >> return maxSum; > alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5 alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11 alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3 alert( getMaxSubSum([1, 2, 3]) ); // 6 alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

Это решение имеет оценку сложности O(n 2 ). Другими словами, если мы увеличим размер массива в 2 раза, время выполнения алгоритма увеличится в 4 раза.

Для больших массивов(1000, 10000 или больше элементов) такие алгоритмы могут приводить к серьёзным «тормозам».

Быстрое решение

Быстрое решение

Идём по массиву и накапливаем текущую частичную сумму элементов в переменной s . Если s в какой-то момент становится отрицательной – присваиваем s=0 . Максимальный из всех s и будет ответом.

Если объяснение недостаточно понятно, посмотрите на код, он вполне лаконичен:

function getMaxSubSum(arr) < let maxSum = 0; let partialSum = 0; for (let item of arr) < // для каждого элемента массива partialSum += item; // добавляем значение элемента к partialSum maxSum = Math.max(maxSum, partialSum); // запоминаем максимум на данный момент if (partialSum < 0) partialSum = 0; // ноль если отрицательное >return maxSum; > alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5 alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11 alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3 alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100 alert( getMaxSubSum([1, 2, 3]) ); // 6 alert( getMaxSubSum([-1, -2, -3]) ); // 0

Этот алгоритм требует ровно 1 проход по массиву и его оценка сложности O(n).

Больше информации об алгоритме тут: Задача поиска максимальной суммы подмассива. Если всё ещё не очевидно как это работает, просмотрите алгоритм в примерах выше, это будет лучше всяких слов.

Функция проверяющая есть ли в массиве подмассив сумма чисел которого равна n

Author24 — интернет-сервис помощи студентам

Всем привет, помогите реализовать булевую функцию которая будет возвращать true если в массиве есть подмассив сумма чисел которого равна n, иначе false. Гарантированно что все элементы массива положительные.

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Функция проверяющая есть ли в массиве пара элементов сумма которых равна элементу между ними
Здравствуйте ! Хотелось бы проверить здесь код одной функции, который я написал. Необходимо.

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

Подмассив массива, сумма элементов которого равна K
Здравствуйте! Не могу понять, какой алгоритм используется для решения задачи, подскажите.

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

2529 / 1248 / 460
Регистрация: 08.11.2016
Сообщений: 3,428
dx3n, массив одномерный?
264 / 183 / 87
Регистрация: 03.05.2020
Сообщений: 790

1 2 3 4 5 6 7 8 9 10 11
bool subarr(int *a,int sz,int n) { for(int i=0; isz; i++) for(int s=0,j=i; jsz; j++) { s+=a[j]; if(s==n) return true; if(s>n) break; } return false; }

Регистрация: 15.06.2020
Сообщений: 64

Annemesski, да одномерный, я тут реализовал эту функцию, но как мне её поменять так, чтобы она ещё и подмассив выводила?
Вот код:

1 2 3 4 5 6 7 8 9
def isSubsetSum(set, n, sum): if sum == 0: return True if n == 0 and sum != 0: return False if set[n - 1] > sum: return isSubsetSum(set, n - 1, sum) return isSubsetSum(set, n - 1, sum) or isSubsetSum(set, n - 1, sum - set[n - 1])

Извините что на python, я просто по быстрому накатал код. n — это длина исходного массива, set — это сам массив, а sum — интересующая нас сумма

Добавлено через 14 минут
Помогите сделать такую функцию, очень срочно надо

264 / 183 / 87
Регистрация: 03.05.2020
Сообщений: 790

1 2 3 4 5 6 7 8 9 10
int* subarr(int *a,int sz,int n) { for(int i=0; isz; i++) for(int s=0,j=i; sn && jsz; j++) { s+=a[j]; if(s==n) return a+j; } return 0; }

Регистрация: 15.06.2020
Сообщений: 64
AnyKey, а как сделать так чтобы на выходе был массив?
264 / 183 / 87
Регистрация: 03.05.2020
Сообщений: 790
dx3n, указатель на него высылает, либо 0, только изменить

[CPP]7 if(s==n) return a+i;

264 / 183 / 87
Регистрация: 03.05.2020
Сообщений: 790
dx3n, указатель на него высылает, либо 0, только изменить

7 if(s==n) return a+i;

Регистрация: 15.06.2020
Сообщений: 64
AnyKey, а как сделать тот же самый код только с vector ?
2529 / 1248 / 460
Регистрация: 08.11.2016
Сообщений: 3,428

Решенеие от AnyKey, добавил возврат индексов массива с какого по какой расположен найденный подмассив.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
bool subarr(int *a, int sz, int n, int *from = nullptr, int *to = nullptr) { for (int i = 0; isz; i++) for (int s = 0, j = i; jsz; j++) { s += a[j]; if (s == n) { if (from != nullptr && to != nullptr) { *from = i; *to = j; } return true; } if (s>n) break; } return false; } int main() { int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int f, t; for (int i = 0; i  10; ++i) std::cout  [i]  <" "; std::cout  ::endl; bool y = subarr(arr, 10, 57, &f, &t); std::cout  <(y ? "YES, sub array places from " : "NO!\n"); if (y) std::cout   <" to "   ::endl; return 0; }

Регистрация: 15.06.2020
Сообщений: 64

Annemesski, нет мне не совсем это нужно. Мне нужен не отрезок, а вообще элементы из массива необязательно расположенные все рядом. Ну грубо говоря «рандомные»

264 / 183 / 87
Регистрация: 03.05.2020
Сообщений: 790

1 2 3 4 5 6 7 8 9 10 11 12 13 14
vectorint> subarr(int *a,int sz,int n) { vectorint> v; for(int i=0; isz; i++) for(int s=0,j=i; sn && jsz; j++) { s+=a[j]; if(s==n) { for(int k=i; kj; k++) v.push_back(a[k]); break; } return v; }

2529 / 1248 / 460
Регистрация: 08.11.2016
Сообщений: 3,428

dx3n, тогда формулируйте правильно: массив — это непрерывнй набор данных, подмассив, соответственно, тоже непрерывный.

Ваша задача получается такой: определить существует ли в массиве такой набор чисел, сумма которых равна некоторому n определяемому пользователем и если существует, то создать новый массив из этих элементов.

Регистрация: 15.06.2020
Сообщений: 64

AnyKey, я так понимаю ваш код может смотреть только по соседним, правильно? просто когда массив = то если я хочу 7 он её не находит (

Добавлено через 1 минуту
Annemesski, да именно так, извините за мою косячную формулировку)

264 / 183 / 87
Регистрация: 03.05.2020
Сообщений: 790
dx3n, см.#13
Регистрация: 15.06.2020
Сообщений: 64

Задача: создать массив из исходного массива такой что сумма его элементов равна заданному числу n.

Добавлено через 36 секунд
Новый массив не обязательно является отрезком из исходного массива

264 / 183 / 87
Регистрация: 03.05.2020
Сообщений: 790
рекурсивно перебором
Регистрация: 15.06.2020
Сообщений: 64
AnyKey, как?
264 / 183 / 87
Регистрация: 03.05.2020
Сообщений: 790
чет хлопотно получилось:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
void find(int k,int s,int *a,int sz,char *use,bool &end,int n,vectorint> &v) { for(int i=0; isz; i++) if(!use[i] && s+a[i]n && !end) { use[i]=1; v.push_back(a[i]); if(s+a[i]n && k+1sz) find(k+1,s+a[i],a,sz,use,end,n,v); if(s+a[i]==n) end=true; else if(!end) { v.pop_back(); use[i]=0; } } } void main() { int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int sz=sizeof(a)/sizeof(int); char *use=(char*)calloc(sz,1); int n=31; vectorint> v; bool end=false; find(0,0,a,sz,use,end,n,v); if(end) { for(int i=0; i(int)v.size(); i++) cout[i]<" "; cout; } free(use); cout; system("pause"); }

Регистрация: 15.06.2020
Сообщений: 64
AnyKey, вы просто мой код не видели) хотя он на питоне и вроде тоже работает:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
array = [] def Sublists(numbers, sublist, n, walkRight, level): if sum(sublist) == n: array.append(sublist) return if len(sublist) == 1: return if walkRight: level += 1 Sublists(numbers, sublist[:len(sublist) - 1], n, walkRight, level) walkRight = False level += 1 Sublists(numbers, sublist[1:len(sublist)], n, walkRight, level) print(array)

Здесь я использовал логику дерева ну и короче как-то так)
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Дан массив чисел, найдите подмассив, сумма которого наибольшая
Дан массив чисел, найдите подмассив, сумма которого наибольшая, и выведите эту сумму Пример.

Функция проверяющая есть ли в массиве указанное число
#include <iostream> #include<ctime> #define N 3 using namespace std; void fillArray(int.

Есть ли в этой последовательности член, сумма цифр которого равна 1
Задана числовая последовательность 2, 4, 8, 16, 23, 28, 38, . Каждый член этой.

Вывести подмассив, сумма элементов которого максимальная LINQ
using System; using System.Linq; public class Program < public static int Puzzle(int input).

Найти строки матрицы, где есть эл-т для которого сумма предшествующих равна сумме следующих за ним элементов
Доброго времени суток всем. Прошу помочь с этими заданиям, написать код в c++ 2. Вывести строки.

Определить, есть ли в этом массиве три числа, сумма которых равна нулю
Дан массив из N целых чисел а1, а2. an. Вам нужно проверить, есть ли в этом массиве три числа.

Или воспользуйтесь поиском по форуму:

C++ подмассив

приёмы написания эффективных алгоритмов (вместо трёх и более циклов всего два или один — максимальная сложность алгоритма указана в условии, О(х)), решать всё всем: все размерности всех одномерных массивов 100000
-в массиве целых чисел найти непрерывный подмассив, сумма элементов которого максимальная; вывести два индекса (начало, конец) и получившуюся сумму ( O )

#include #include #include #include using namespace std; const int max_kl=100000; int main() < int n,l=0,r,ts=0,ms=0,temp; int mas[max_kl]; bool b1=0; srand((unsigned)time(NULL)); cout ";cin>>n;cout > mas[i];*/ mas[i]=rand()%(99+99)-99; cout cout 0) if(mas[i]>ts) > if(b1==1) < for(int i=1;iif(ts>ms) < ms=ts;r=i;l=temp; >> cout l: " else cout "

Проблема состиит в том, что если например массив заполнить так -7 5 -9 то программа не работает. Объясните причину, кому не длень разбираться, и , если можно, методы преодоления этого. Зарание спасибо.

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

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