Bài 17: Kỹ thuật hai con trỏ và cửa sổ trượt trong C++ và Python: tìm cặp, đoạn con dài nhất, ngắn nhất trong O(n)
Lời mở đầu
Rất nhiều bài trên mảng có dạng: “tìm cặp phần tử thỏa…”, “tìm đoạn con dài nhất / ngắn nhất thỏa…”, “đếm số đoạn con thỏa…”. Cách tự nhiên là duyệt mọi cặp $(i, j)$, mất $O(n^2)$: với $n = 10^5$ đã là $10^{10}$ phép tính, TLE chắc chắn. Kỹ thuật hai con trỏ (two pointers) khai thác một tính chất đặc biệt của các bài này: khi một đầu dịch sang phải, đầu kia chỉ cần dịch theo một chiều, không bao giờ phải quay lại. Vì mỗi con trỏ đi tối đa $n$ bước, tổng thời gian chỉ còn $O(n)$.
Bài này nối tiếp tự nhiên với mảng cộng dồn ở bài 13 và tìm kiếm nhị phân ở bài 16: nhiều bài giải được bằng cả ba cách, nhưng hai con trỏ thường ngắn gọn và nhanh nhất.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Vì sao hai con trỏ chỉ tốn O(n)?
Đoạn code hai con trỏ thường có hai vòng lặp lồng nhau, nhìn qua tưởng là $O(n^2)$:
int l = 0;
for(int r = 0; r < n; r++){ // con trỏ phải đi từ 0 tới n - 1
thêm a[r] vào cửa sổ;
while(cửa sổ [l, r] vi phạm điều kiện){
bỏ a[l] khỏi cửa sổ; l++; // con trỏ trái chỉ tăng, không bao giờ giảm
}
cập nhật đáp án với cửa sổ [l, r];
}Nhưng hãy đếm tổng số lần l++ chạy trong cả chương trình: vì l bắt đầu từ 0, chỉ tăng và không vượt quá $n$, nên l++ chạy tối đa $n$ lần tính chung cho mọi vòng, không phải $n$ lần cho mỗi $r$. Tương tự r chạy $n$ lần. Tổng cộng tối đa $2n$ bước, tức $O(n)$. Cách đếm “tổng số bước của cả chương trình” như vậy gọi là phân tích khấu hao.
Phần 2Hai con trỏ ngược chiều: tìm cặp có tổng bằng x
Bài toán: cho mảng tăng ngặt $a$ và số $x$, đếm số cặp $i < j$ có $a_i + a_j = x$. Đặt i ở đầu mảng, j ở cuối mảng, xét tổng $s = a_i + a_j$:
- $s = x$: tìm được một cặp; vì các số phân biệt nên $a_i$ không thể ghép với ai khác ngoài $a_j$, dịch cả hai:
i++, j--. - $s < x$: tổng nhỏ quá. $a_j$ đã là số lớn nhất có thể ghép với $a_i$ mà vẫn nhỏ hơn $x$, nên $a_i$ không ghép được với ai, bỏ nó:
i++. - $s > x$: tổng lớn quá, tương tự bỏ $a_j$:
j--.
Mỗi bước loại bỏ ít nhất một phần tử, nên tối đa $n$ bước.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long x;
cin >> n >> x;
vector<long long> a(n);
for(auto &v : a) cin >> v;
int i = 0, j = n - 1, dem = 0;
while(i < j){
long long s = a[i] + a[j];
if(s == x){ dem++; i++; j--; }
else if(s < x) i++;
else j--;
}
cout << dem;
return 0;
}n, x = map(int, input().split())
a = list(map(int, input().split()))
i, j, dem = 0, n - 1, 0
while i < j:
s = a[i] + a[j]
if s == x:
dem += 1
i += 1
j -= 1
elif s < x:
i += 1
else:
j -= 1
print(dem)Mô phỏng trực quan. Câu hỏi các bạn hay hỏi nhất ở phần này: "dịch con trỏ như vậy có bỏ sót cặp nào không?". Em xem bảng mọi cặp bên dưới: mỗi bước, cả một hàng hoặc một cột bị gạch đi với lý do chắc chắn, nên đến cuối bảng sạch trơn mà không cặp nào bị bỏ sót.
Phần 3Cửa sổ trượt: đoạn con dài nhất có tổng không vượt quá S
Bài toán: cho dãy $n$ số không âm và số $S$. Tìm độ dài lớn nhất của một đoạn con liên tiếp có tổng $\le S$. Hình dung một cửa sổ $[l, r]$ trượt trên mảng: mỗi bước mở rộng cửa sổ sang phải một ô (r++); nếu tổng vượt $S$ thì thu hẹp từ bên trái (l++) cho tới khi hợp lệ trở lại. Sau mỗi bước, $[l, r]$ chính là đoạn dài nhất kết thúc tại $r$ thỏa điều kiện.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long S;
cin >> n >> S;
vector<long long> a(n);
for(auto &v : a) cin >> v;
int l = 0, best = 0;
long long tong = 0;
for(int r = 0; r < n; r++){
tong += a[r];
while(tong > S){
tong -= a[l];
l++;
}
best = max(best, r - l + 1);
}
cout << best;
return 0;
}n, S = map(int, input().split())
a = list(map(int, input().split()))
l = best = tong = 0
for r in range(n):
tong += a[r]
while tong > S:
tong -= a[l]
l += 1
best = max(best, r - l + 1)
print(best)Xem cửa sổ trượt chạy: thử cả hai bài toán anh em song sinh: dài nhất có tổng $\le S$, và ngắn nhất có tổng $\ge S$. Hai bài chỉ khác nhau chỗ cập nhật đáp án nằm trong hay ngoài vòng while.
Phần 4Cửa sổ kích thước cố định
Khi đề hỏi về các đoạn có đúng $k$ phần tử liên tiếp (tổng lớn nhất của $k$ ngày liên tiếp, trung bình $k$ số liên tiếp…), cửa sổ không co giãn mà chỉ trượt: mỗi bước thêm phần tử mới ở bên phải và bỏ phần tử cũ ở bên trái. Tổng mới = tổng cũ $+ a_r - a_{r-k}$, chỉ một phép tính thay vì cộng lại $k$ số.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
vector<long long> a(n);
for(auto &v : a) cin >> v;
long long tong = 0;
for(int i = 0; i < k; i++) tong += a[i];
long long best = tong;
for(int r = k; r < n; r++){
tong += a[r] - a[r - k];
best = max(best, tong);
}
cout << best;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
tong = sum(a[:k])
best = tong
for r in range(k, n):
tong += a[r] - a[r - k]
best = max(best, tong)
print(best)Phần 5Kết hợp mảng đếm: đoạn con có các phần tử phân biệt
Điều kiện của cửa sổ không nhất thiết là tổng. Với bài “đoạn con dài nhất có các phần tử đôi một khác nhau”, ta dùng mảng đếm cnt[v] = số lần giá trị $v$ có mặt trong cửa sổ (như bài 13, hoặc map nếu giá trị lớn). Thêm $a_r$ vào: cnt[a[r]]++; nếu cnt[a[r]] > 1 tức cửa sổ có phần tử lặp, thu hẹp từ trái cho tới khi cnt[a[r]] == 1. Tính đơn điệu vẫn đúng: đoạn không có phần tử lặp thì mọi đoạn con của nó cũng không có.
Đoạn con dài nhất có các phần tử phân biệt
#include <bits/stdc++.h>
using namespace std;
int cnt[1000005];
int main(){
int n;
cin >> n;
vector<int> a(n);
for(int &v : a) cin >> v; // 0 ≤ a[i] ≤ 10^6
int l = 0, best = 0;
for(int r = 0; r < n; r++){
cnt[a[r]]++;
while(cnt[a[r]] > 1){ // a[r] bị lặp trong cửa sổ
cnt[a[l]]--;
l++;
}
best = max(best, r - l + 1);
}
cout << best;
return 0;
}from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
cnt = defaultdict(int)
l = best = 0
for r in range(n):
cnt[a[r]] += 1
while cnt[a[r]] > 1:
cnt[a[l]] -= 1
l += 1
best = max(best, r - l + 1)
print(best)dem += r - l + 1 là xong, vẫn $O(n)$. Kết quả có thể tới $\frac{n(n+1)}{2} \approx 5 \cdot 10^9$, nhớ dùng long long.- Đoạn Con (DPSUBSEG) (Dễ)
- Sửa Đèn (Dễ)
- Sắp Xếp Chẵn Trái Lẻ Phải (Dễ)
- Dương Âm Xen Kẽ (Trung bình)
- Hộp Quà (HOPQUA) (Trung bình)
Mô phỏng trực quan. Kết hợp cửa sổ trượt với mảng đếm thì cần theo dõi cùng lúc hai thứ: cửa sổ [l, r] và mảng cnt. Em bấm Tiếp để thấy mỗi khi gặp số trùng, l nhích dần sang phải cho tới khi cửa sổ sạch trở lại, và l không bao giờ phải lùi.
Bài tậpLuyện hai con trỏ
Cho $n$ số nguyên ($n \le 10^5$, chưa sắp xếp) và số $x$. Có tồn tại hai vị trí $i \ne j$ với $a_i + a_j = x$ không? In YES hoặc NO.
6 15
8 3 11 5 2 7YES💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long x;
cin >> n >> x;
vector<long long> a(n);
for(auto &v : a) cin >> v;
sort(a.begin(), a.end());
int i = 0, j = n - 1;
while(i < j){
long long s = a[i] + a[j];
if(s == x){ cout << "YES"; return 0; }
if(s < x) i++; else j--;
}
cout << "NO";
return 0;
}n, x = map(int, input().split())
a = sorted(map(int, input().split()))
i, j = 0, n - 1
ok = False
while i < j:
s = a[i] + a[j]
if s == x:
ok = True
break
if s < x:
i += 1
else:
j -= 1
print("YES" if ok else "NO")Cho $n$ số nguyên ($n \le 10^5$) và $x$. Đếm số cặp $i < j$ có $a_i + a_j \le x$.
5 9
5 1 7 3 47💡 Gợi ý
j - i rồi i++; ngược lại j--. Kết quả dùng long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long x;
cin >> n >> x;
vector<long long> a(n);
for(auto &v : a) cin >> v;
sort(a.begin(), a.end());
int i = 0, j = n - 1;
long long dem = 0;
while(i < j){
if(a[i] + a[j] <= x){ dem += j - i; i++; }
else j--;
}
cout << dem;
return 0;
}n, x = map(int, input().split())
a = sorted(map(int, input().split()))
i, j, dem = 0, n - 1, 0
while i < j:
if a[i] + a[j] <= x:
dem += j - i
i += 1
else:
j -= 1
print(dem)Cho doanh thu $n$ ngày ($n \le 10^6$, có thể âm). Tìm tổng doanh thu lớn nhất của $k$ ngày liên tiếp.
10 3
3 -1 4 1 5 -9 2 6 5 314💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> a(n);
for(auto &v : a) cin >> v;
long long s = 0;
for(int i = 0; i < k; i++) s += a[i];
long long best = s;
for(int r = k; r < n; r++){
s += a[r] - a[r - k];
best = max(best, s);
}
cout << best;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a[:k])
best = s
for r in range(k, n):
s += a[r] - a[r - k]
best = max(best, s)
print(best)Cho hai dãy đã sắp xếp không giảm, độ dài $n$ và $m$ ($\le 10^5$). In dãy gồm tất cả phần tử của cả hai, sắp xếp không giảm, trong $O(n + m)$.
3 4
1 4 9
2 3 4 101 2 3 4 4 9 10💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<long long> a(n), b(m), c;
for(auto &v : a) cin >> v;
for(auto &v : b) cin >> v;
int i = 0, j = 0;
while(i < n && j < m){
if(a[i] <= b[j]) c.push_back(a[i++]);
else c.push_back(b[j++]);
}
while(i < n) c.push_back(a[i++]);
while(j < m) c.push_back(b[j++]);
for(size_t t = 0; t < c.size(); t++) cout << c[t] << (t + 1 < c.size() ? " " : "\n");
return 0;
}n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
i = j = 0
c = []
while i < n and j < m:
if a[i] <= b[j]:
c.append(a[i]); i += 1
else:
c.append(b[j]); j += 1
c += a[i:] + b[j:]
print(*c)Cho $n$ số nguyên dương ($n \le 10^6$) và $S$. Tìm độ dài ngắn nhất của đoạn con liên tiếp có tổng $\ge S$; nếu không có in 0.
8 15
2 5 1 8 3 6 1 43💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long S;
cin >> n >> S;
vector<long long> a(n);
for(auto &v : a) cin >> v;
int l = 0, best = INT_MAX;
long long s = 0;
for(int r = 0; r < n; r++){
s += a[r];
while(s >= S){
best = min(best, r - l + 1);
s -= a[l++];
}
}
cout << (best == INT_MAX ? 0 : best);
return 0;
}n, S = map(int, input().split())
a = list(map(int, input().split()))
l, s, best = 0, 0, float('inf')
for r in range(n):
s += a[r]
while s >= S:
best = min(best, r - l + 1)
s -= a[l]
l += 1
print(0 if best == float('inf') else best)Cho $n$ số nguyên không âm ($n \le 10^6$) và $S$. Đếm số đoạn con liên tiếp (khác rỗng) có tổng $\le S$.
4 5
1 2 3 46💡 Gợi ý
r - l + 1 đoạn kết thúc tại $r$ thỏa điều kiện. Các đoạn ở ví dụ: [1], [2], [3], [4], [1, 2], [2, 3].Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long S;
cin >> n >> S;
vector<long long> a(n);
for(auto &v : a) cin >> v;
int l = 0;
long long s = 0, dem = 0;
for(int r = 0; r < n; r++){
s += a[r];
while(s > S) s -= a[l++];
dem += r - l + 1;
}
cout << dem;
return 0;
}n, S = map(int, input().split())
a = list(map(int, input().split()))
l = s = dem = 0
for r in range(n):
s += a[r]
while s > S:
s -= a[l]
l += 1
dem += r - l + 1
print(dem)Cho xâu $s$ gồm chữ cái thường (độ dài $\le 10^6$). Tìm độ dài xâu con liên tiếp dài nhất không có ký tự nào lặp lại.
abcabcbb3💡 Gợi ý
cnt[c - 'a']. Ví dụ: “abc”.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int cnt[26] = {0}, l = 0, best = 0;
for(int r = 0; r < (int)s.size(); r++){
cnt[s[r] - 'a']++;
while(cnt[s[r] - 'a'] > 1) cnt[s[l++] - 'a']--;
best = max(best, r - l + 1);
}
cout << best;
return 0;
}s = input().strip()
cnt = [0] * 26
l = best = 0
for r, ch in enumerate(s):
cnt[ord(ch) - 97] += 1
while cnt[ord(ch) - 97] > 1:
cnt[ord(s[l]) - 97] -= 1
l += 1
best = max(best, r - l + 1)
print(best)Một hàng $n$ cây ($n \le 10^6$), cây thứ $i$ thuộc loại $a_i$ ($0 \le a_i \le 10^6$). Tìm đoạn cây liên tiếp dài nhất chứa không quá $k$ loại cây khác nhau.
9 2
1 2 1 3 3 3 2 2 36💡 Gợi ý
cnt và biến loai = số giá trị có cnt > 0 trong cửa sổ. Thêm $a_r$: nếu cnt[a[r]] tăng từ 0 lên 1 thì loai++. Khi loai > k, bỏ $a_l$; nếu cnt[a[l]] giảm về 0 thì loai--. Ví dụ: đoạn 3 3 3 2 2 3 có 2 loại.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int cnt[1000005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int &v : a) cin >> v;
int l = 0, loai = 0, best = 0;
for(int r = 0; r < n; r++){
if(cnt[a[r]]++ == 0) loai++;
while(loai > k){
if(--cnt[a[l]] == 0) loai--;
l++;
}
best = max(best, r - l + 1);
}
cout << best;
return 0;
}from collections import defaultdict
n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt = defaultdict(int)
l = loai = best = 0
for r in range(n):
if cnt[a[r]] == 0:
loai += 1
cnt[a[r]] += 1
while loai > k:
cnt[a[l]] -= 1
if cnt[a[l]] == 0:
loai -= 1
l += 1
best = max(best, r - l + 1)
print(best)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét