Техника двух указателей
Узнайте, как работает техника двух указателей
Введение
Предположим, нам дан массив и число . Мы хотим найти подмассив максимальной длины такой, что сумма его элементов не превышает .
Узнайте, как работает техника двух указателей
Предположим, нам дан массив и число . Мы хотим найти подмассив максимальной длины такой, что сумма его элементов не превышает .
Другими словами, нам нужно найти индексы и такие, что
и значение как можно больше.
Зафиксируем левую границу и найдём максимальную правую границу такую, что
Обозначим это значение как .
Тогда ответ на задачу равен
Прямолинейное решение — пробовать каждую левую границу независимо и расширять правую границу как можно дальше.
Это можно реализовать за :
Это работает, но слишком медленно для больших .
Ключевое наблюдение:
Наблюдение 1. для всех .
Это означает, что если мы сдвигаем левую границу вправо, лучшая возможная правая граница никогда не сдвигается назад.
Поэтому вместо того, чтобы перезапускать поиск для каждого , мы можем держать правый указатель на месте и продолжать двигать его только вперёд.
Именно это делает технику двух указателей эффективной.
Мы поддерживаем два указателя:
i = левая граница текущего отрезкаj = правая граница текущего отрезкаМы также поддерживаем текущую сумму отрезка .
Для каждой позиции i мы двигаем j как можно дальше вправо, пока сумма остаётся не больше . Затем записываем opt[i] = j.
Перед переходом к следующему i мы вычитаем a[i] из текущей суммы.
Поскольку каждый указатель двигается только вперёд, общее число перемещений не превышает для каждого указателя, имея временную сложность .
Пусть
Начинаем с i = 1, j = 0, sum = 0.
j, пока возможно:
2 sum = 21 sum = 33, потому что сумма стала бы 6Значит opt[1] = 2, и отрезок равен .
Теперь сдвигаем i на 2:
a[1] = 2, значит sum = 1j:
3 sum = 42, потому что сумма стала бы 6Значит opt[2] = 3, и отрезок равен .
Продолжая таким образом, мы находим лучший допустимый отрезок.
Задача: Дан отсортированный массив , посчитать количество пар таких, что и .
Идея: Использовать два указателя с противоположных концов. Если , то все пары допустимы, поэтому мы добавляем и двигаем l. Иначе двигаем r.
Задача: Даны два отсортированных массива и , вывести все элементы в отсортированном порядке.
Идея: Держать по одному указателю в каждом массиве. На каждом шаге сравнивать текущие элементы и брать меньший.
Задача: Дана строка и шаблон , найти наименьшую подстроку , которая содержит все символы .
Идея: Расширять правый указатель, пока текущее окно не будет содержать все нужные символы. Затем двигать левый указатель, чтобы сделать окно как можно меньше.
// i: левый индекс текущего интервала
// j: правый индекс текущего интервала
// (максимальный r такой, что sum <= K)
for (int i = 1; i <= n; i++) {
int j = i - 1;
int sum = 0;
while (j + 1 <= n && sum + a[j + 1] <= K) {
j++;
sum += a[j];
}
opt[i] = j;
}
for (int i = 1, j = 0, sum = 0; i <= n; i++) {
while (j + 1 <= n && sum + a[j + 1] <= K) {
j++;
sum += a[j];
}
opt[i] = j;
sum -= a[i];
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, K;
cin >> n >> K;
vector<int> a(n + 1), opt(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int j = 0;
int sum = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
while (j + 1 <= n && sum + a[j + 1] <= K) {
j++;
sum += a[j];
}
opt[i] = j;
ans = max(ans, opt[i] - i + 1);
sum -= a[i];
}
cout << ans << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, K;
cin >> n >> K;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
long long ans = 0;
int l = 0, r = n - 1;
while (l < r) {
if (a[l] + a[r] <= K) {
ans += (r - l);
l++;
} else {
r--;
}
}
cout << ans << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> A(n), B(m);
for (int i = 0; i < n; i++) {
cin >> A[i];
}
for (int j = 0; j < m; j++) {
cin >> B[j];
}
int i = 0, j = 0;
vector<int> merged;
while (i < n && j < m) {
if (A[i] < B[j]) {
merged.push_back(A[i++]);
} else {
merged.push_back(B[j++]);
}
}
while (i < n) {
merged.push_back(A[i++]);
}
while (j < m) {
merged.push_back(B[j++]);
}
for (int x : merged) {
cout << x << " ";
}
cout << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, p;
cin >> s >> p;
vector<int> need(256, 0), have(256, 0);
for (char c : p) {
need[c]++;
}
int required = p.size();
int l = 0, formed = 0, best_len = 1e9, best_l = 0;
for (int r = 0; r < (int)s.size(); r++) {
char c = s[r];
have[c]++;
if (need[c] > 0 && have[c] <= need[c]) {
formed++;
}
while (formed == required) {
if (r - l + 1 < best_len) {
best_len = r - l + 1;
best_l = l;
}
have[s[l]]--;
if (need[s[l]] > 0 && have[s[l]] < need[s[l]]) {
formed--;
}
l++;
}
}
if (best_len == 1e9) {
cout << "-1\n";
} else {
cout << s.substr(best_l, best_len) << "\n";
}
return 0;
}