Для нахождения непрерывного подмассива в массиве, сумма которого равна заданному числу, можно использовать алгоритм двух указателей (two-pointer algorithm) или алгоритм "скользящего окна" (sliding window algorithm). Рассмотрим оба подхода.
- Алгоритм двух указателей:
int[] arr = {2, 3, 6, 7, 9, 11};
int sum = 16;
int left = 0; // левый указатель
int right = 0; // правый указатель
int currentSum = 0;
while (right < arr.length) {
currentSum += arr[right];
while (currentSum > sum && left <= right) {
currentSum -= arr[left];
left++;
}
if (currentSum == sum) {
System.out.println("Найден подмассив: [" + left + ", " + right + "]");
return;
}
right++;
}
System.out.println("Подмассив не найден");
В данном примере мы используем два указателя left и right, чтобы определить непрерывный подмассив, сумма которого равна заданному числу sum. Сначала оба указателя указывают на первый элемент массива. Затем мы перебираем каждый элемент массива при помощи указателя right и добавляем его к текущей сумме currentSum. Если значение currentSum становится больше sum, то мы вычитаем из текущей суммы элементы, находящиеся в левой части подмассива при помощи указателя left. Если значение currentSum становится равным sum, то выводим найденный подмассив. Если же указатель right доходит до конца массива и нужный подмассив не найден, то выводим сообщение о том, что подмассив не найден.
- Алгоритм "скользящего окна":
int[] arr = {2, 3, 6, 7, 9, 11};
int sum = 16;
int left = 0; // начало подмассива
int right = 0; // конец подмассива
int currentSum = arr[0];
while (right < arr.length && left <= right) {
if (currentSum == sum) {
System.out.println("Найден подмассив: [" + left + ", " + right + "]");
return;
} else if (currentSum < sum) {
right++;
if (right < arr.length) {
currentSum += arr[right];
}
} else {
currentSum -= arr[left];
left++;
}
}
System.out.println("Подмассив не найден");
В данном примере мы используем алгоритм "скользящего окна", который работает похожим образом на алгоритм двух указателей. Здесь переменная left указывает на начало непрерывного подмассива, а переменная right - на его конец. Значение суммы подмассива сохраняется в переменной currentSum. Алгоритм работает следующим образом: если значение currentSum равно заданному числу sum, то выводим найденный подмассив. Если же currentSum меньше sum, то мы увеличиваем значение right и добавляем соответствующий элемент к сумме currentSum. Если же currentSum больше sum, то мы уменьшаем значение left и вычитаем соответствующий элемент из суммы currentSum. Если указатель right доходит до конца массива и нужный подмассив не найден, то выводим сообщение о том, что подмассив не найден.
Оба подхода имеют временную сложность O(n) и являются
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov