Introduction
Suppose we are given an array and a number . We want to find a subarray of maximum length such that the sum of its elements does not exceed .
Suppose we are given an array and a number . We want to find a subarray of maximum length such that the sum of its elements does not exceed .
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:
In other words, we need to find indices and such that
and the value is as large as possible.
Let us fix the left boundary and find the maximum right boundary such that
Denote this value by .
Then the answer to the problem is
A straightforward solution is to try every left boundary independently and extend the right boundary as far as possible.
This can be implemented in :
This works, but it is too slow for large .
The key observation is:
Observation 1. for all .
This means that if we move the left boundary to the right, the best possible right boundary never moves backward.
So instead of restarting the search for every , we can keep the right pointer where it is and continue moving it only forward.
This is exactly what makes the two pointers technique efficient.
We maintain two pointers:
i = left boundary of the current segmentj = right boundary of the current segmentWe also maintain the current sum of the segment .
For each position i, we move j as far to the right as possible while the sum remains at most . Then we record opt[i] = j.
Before moving to the next i, we remove a[i] from the current sum.
Since each pointer moves only forward, the total number of moves is at most for each pointer, having time complexity of .
Problem: Given a sorted array , count the number of pairs such that and .
Idea: Use two pointers from opposite ends. If , then all pairs are valid, so we add and move l. Otherwise, we move r.
Problem: Given two sorted arrays and , output all elements in sorted order.
Idea: Keep one pointer in each array. At each step, compare the current elements and take the smaller one.
Problem: Given a string and a pattern , find the smallest substring of that contains all characters of .
Idea: Expand the right pointer until the current window contains all needed characters. Then move the left pointer to make the window as small as possible.
// i: left index of current interval
// j: right index of current interval
// (maximum r such that 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;
}