I. Tổng quan về kĩ thuật Two Pointers

Trong lập trình nói chung và lập trình thi đấu nói riêng, kĩ thuật hai con trỏ (two pointers) là một kĩ thuật rất hiệu quả để giải quyết các bài toán trên mảng hoặc chuỗi. Kĩ thuật này giúp tiết kiệm không gian lưu trữ, giảm thời gian chạy của giải thuật rất hiệu quả.

Vậy kĩ thuật hai con trỏ là gì? Đúng như tên gọi của nó, kĩ thuật này sử dụng hai con trỏ đồng thời để kiểm soát hai vị trí trên mảng hoặc chuỗi. Tuy nhiên khác với khái niệm con trỏ mà chúng ta thường biết (là một biến trỏ vào địa chỉ trong bộ nhớ máy tính của một đối tượng), con trỏ trong kĩ thuật này chỉ đơn giản là những biến kiểm soát vị trí trên mảng hoặc chuỗi, trong đó có một biến luôn luôn không vượt quá biến còn lại. Hình vẽ dưới đây là một minh họa:

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

Trong rất nhiều bài toán trên mảng hoặc chuỗi, chúng ta sẽ phải quét qua các cặp giá trị, hoặc những đoạn liên tiếp trên dãy số. Nếu như sử dụng những vòng lặp lồng nhau, hoặc kết hợp các cấu trúc dữ liệu để kiểm soát các đoạn giá trị thì thời gian chạy của giải thuật sẽ không thể đảm bảo. Vậy giải pháp là gì? Chính là kĩ thuật two pointers - một giải pháp vừa tiết kiệm không gian lưu trữ, vừa giảm thời gian thực thi của giải thuật (thông thường xuống

O (n)

). Khi sử dụng two-pointers, thay vì chỉ truy cập được một phần tử của dãy, ta sẽ truy cập được đồng thời hai phần tử của dãy ở mỗi lần lặp, qua đó giảm số thao tác cần thực hiện đi rất nhiều.

Kĩ thuật này có thể chia làm ba dạng thường gặp:

Slow And Fast: Một con trỏ chạy với tốc độ chậm, một con trỏ chạy với tốc độ nhanh.
Left & Right Boundary: Hai con trỏ di chuyển ngược chiều nhau.
Sliding Windows: Hai con trỏ di chuyển với cùng một tốc độ, về cùng một phía.

Sau đây chúng ta sẽ cùng phân tích ý tưởng của cả ba dạng toán thường gặp của kĩ thuật này thông qua những bài tập điển hình của chúng.

II. Dạng bài Slow And Fast

1. Giải thuật tổng quát

Trong dạng bài tập này, ta sẽ luôn luôn có một con trỏ đi phía trước với tốc độ chậm, và một con trỏ đi phía sau với tốc độ nhanh hơn. Thông thường, ở mỗi lần lặp, con trỏ phía sau sẽ luôn tăng lên, còn con trỏ phía trước thì chỉ tăng lên khi thỏa mãn một tập điều kiện nào đó.

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Giải thuật tổng quát có thể viết mã giả như sau:












void slow_and_fast()
{
    pointer_1 = {chỉ số đầu};
    for (pointer_2 = {chỉ số đầu}; pointer_2 <= {chỉ số cuối}; ++pointer_2)
    {
        // Con trỏ thứ nhất chỉ tăng lên khi thỏa mãn một điều kiện nào đó.
        if ({pointer_1 thỏa mãn điều kiện})
            {Tăng pointer_1};

        {Xử lý logic sau khi tăng - giảm các con trỏ};
    }
}

Trong mã giả trên, các yếu tố có thể thay đổi tùy theo từng người lập trình và từng bài toán, nhưng ý tưởng thì vẫn không thay đổi. Ví dụ, vòng lặp for có thể thay bằng vòng lặp while, hay việc xử lý logic có thể đưa lên trước hoặc sau khi dịch chuyển con trò,…Ngoài ra, trong những bài toán phức tạp, có thể con trỏ phía sau cũng sẽ chỉ tăng lên khi đáp ứng được một tập điều kiện nào đó, vì vậy điều quan trọng ở đây là các bạn hiểu được ý tưởng thuật toán!

2. Bài toán ví dụ

Bài toán 1

Cho trước mảng số nguyên

A

đã sắp xếp tăng dần.

Yêu cầu: Hãy loại bỏ các phần tử trùng lặp trong dãy và đưa ra độ dài của dãy mới?

Input:

Dòng đầu tiên chứa số nguyên dương
$n$ - kích thước dãy số.
Dòng thứ hai chứa
$n$ số nguyên
$a_{1}, a_{2}, \dots, a_{n}$ phân tách nhau bởi dấu cách - các phần tử dãy số.

Ràng buộc:

$1 \leq n \leq 10^{5}$ .

Output:

In ra kích thước của dãy số sau khi loại bỏ toàn bộ phần tử trùng lặp.

Sample Input:

10
0 0 1 1 1 2 2 3 3 4

Sample Output:

Ý tưởng

Bởi dãy số đã cho đã được sắp xếp tăng dần, nên các phần tử giống nhau chắc chắn sẽ đứng cạnh nhau.

Duy trì hai con trỏ

slow

và

fast

để kiểm soát các phần tử trên dãy. Con trỏ

fast

sẽ duyệt qua tất cả các phần tử trên dãy, và con trỏ

slow

sẽ chạy phía sau

fast

và kiểm soát luôn kích thước của đoạn phần tử bằng với

a_{fast}

. Mỗi lần chạy qua, ta sẽ gán luôn

a_{slow} = a_{fast}

để coi như "đặt cờ".

Kết quả cuối cùng chính là

slow

Độ phức tạp:

O (n)

Cài đặt

#include <bits/stdc++.h>

using namespace std;

main()
{
    int n;
    cin >> n;

    vector < int > a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    int slow = 0;
    for (int fast = 1; fast < n; ++fast)
        // Nếu phần tử hiện tại không bị trùng lặp.
        if (num[fast] != num[slow])
        {
            // Dịch chuyển con trỏ slow lên 1 vị trí.
            // Copy vị trí hiện tại vào vị trí slow.
            ++slow;
            num[slow] = num[fast];
        }

    cout << slow + 1;

    return 0;
}

Bài toán 2

Cho dãy số

A

gồm

n

phần tử nguyên. Một đoạn con liên tục của dãy

A

là một hoặc nhiều phần tử liên tục lấy từ dãy

A

. Đoạn con liên tục được gọi là hoàn hảo nếu như nó chứa không quá

k

số nguyên phân biệt.

Yêu cầu: Hãy tìm đoạn con liên tục hoàn hảo dài nhất của dãy

A ?

Input:

Dòng đầu tiên chứa hai số nguyên dương
$n$ và
$k$ .
Dòng thứ hai chứa
$n$ số nguyên không âm
$a_{1}, a_{2}, . . ., a_{n}$ phân tách nhau bởi dấu cách.

Ràng buộc:

$1 \leq k \leq n \leq 5 \times 10^{5}$ .
$0 \leq a_{i} \leq 10^{6}; \forall i : 1 \leq i \leq n$ .

Subtasks:

Subtask
$1$ (
$50 %$ số điểm):
$1 \leq n \leq 100$ .
Subtask
$2$ (
$50 %$ số điểm): Không có ràng buộc gì thêm.

Output:

Đưa ra hai số nguyên
$l$ và
$r$ – chỉ số bắt đầu và kết thúc của đoạn con liên tục hoàn hảo dài nhất. Nếu như tồn tại nhiều đoạn con thỏa mãn, in ra đoạn con có chỉ số
$l$ nhỏ nhất.

Sample Input 1:

3 2
1 2 3

Sample Output 1:

1 2

Ý tưởng

Subtask 1

Duyệt qua tất cả các đoạn con và áp dụng kĩ thuật đếm phân phối để tìm ra đoạn con hoàn hảo dài nhất.

Độ phức tạp:

O (n^{2})

Subtask 2

Áp dụng kĩ thuật Hai con trỏ. Đặt

m a r k [x]

là vị trí xuất hiện cuối cùng của giá trị

x

khi trong đoạn con đang xét. Ta sử dụng hai con trỏ

i

và

j

để duyệt dãy con như sau:

Xét phần tử
$j,$ nếu
$a [j]$ chưa xuất hiện thì tăng
$c n t$ lên
$1$ (biến
$c n t$ dùng để duy trì số lượng phần tử khác nhau trong đoạn con đang xét). Luôn luôn đặt
$m a r k [a_{j}] = j$ sau khi duyệt tới
$a_{j}$ .
Tới một vị trí
$j$ nào đó mà
$c n t > k \to$ Dừng vòng lặp này tại đây, lúc đó đoạn
$[i, j - 1]$ chính là đoạn có đúng
$k$ phần tử khác nhau (đạt tối đa). Ta cập nhật độ dài đoạn con hoàn hảo bằng
$j - i$ .
Tiếp theo ta cần dịch con trỏ
$i$ lên trên sao cho số lượng phần tử phân biệt trong đoạn
$[i, j - 1]$ lại giảm xuống nhỏ hơn hoặc bằng
$k$ . Dịch
$i$ lên, nếu như
$i = m a r k [a_{i}]$ nghĩa là phần tử
$a_{i}$ không còn tồn tại trong đoạn con nữa (vì ta lưu vị trí xuất hiện cuối cùng của
$a_{i},$ nếu
$i < m a r k [a_{i}]$ nghĩa là phía sau vẫn có giá trị bằng
$a_{i}$ nên
$a_{i}$ chưa bị loại đi), lúc này ta giảm
$c n t$ đi
$1$ và cập nhật
$m a r k [a_{i}] = 0$ .
Lặp lại bước
$1$ tới khi hết dãy, ta sẽ thu được độ dài của đoạn con hoàn hảo dài nhất. Lưu ý đề bài yêu cầu đưa ra vị trí bắt đầu và vị trí kết thúc của đoạn con hoàn hảo dài nhất xuất hiện đầu tiên trong dãy, nên nếu như có một đoạn con hoàn hảo mới xuất hiện và có độ dài lớn hơn hẳn độ dài của đoạn con hoàn hảo trước đó, thì ta mới cập nhật vị trí bắt đầu và kết thúc.

Độ phức tạp:

O (n)

Cài đặt
























































#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 5e5 + 10, max_value = 1e6 + 10;
int N, K, a[maxn], mark[max_value];

void enter()
{
    
    cin >> N >> K;
    for (int i = 1; i <= N; ++i)
        cin >> a[i];
}

void solution()
{
    int i = 1, j = 1, max_length = 0;
    int cnt = 0, left = 0, right = 0;

    while (i <= j && j <= N)
    {
        while (j <= N && cnt <= K)
        {
            if (mark[a[j]] == 0)
                ++cnt;
            mark[a[j]] = j;
            if (cnt <= K) // Nếu cnt đã lớn hơn K thì không tăng j lên nữa => Đoạn [i, j - 1] là 1 đoạn con hoàn hảo
                ++j;
        }

        if (max_length < j - i) // Tối ưu hóa giá trị max_length và cập nhật vị trí đoạn hoàn hảo dài nhất.
            max_length = j - i, left = i, right = j - 1;

        while (i <= j && cnt > K) // Dịch i lên trên để giảm số lượng phần tử phân biệt đi
        {
            if (i == mark[a[i]])
                --cnt, mark[a[i]] = 0;
            ++i;
        }
    }

    cout << left << ' ' << right;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    enter();
    solution();

    return 0;
}

III. Dạng Left & Right Boundary

1. Giải thuật tổng quát

Trong dạng bài này, ta sẽ sử dụng hai con trỏ, một con trỏ đi từ đầu dãy tiến lên, và một con trỏ đi từ cuối dãy lùi xuống (tất nhiên chỉ dịch chuyển khi thỏa mãn điều kiện nào đó). Chúng sẽ liên tục di chuyển cho tới khi gặp nhau ở giữa dãy số.

Dạng bài này có thể được biến đổi nâng cao thêm như sau:

Hai con trỏ tạo thành một đoạn trong dãy số để xử lý logic.
Hai con trỏ sẽ mang theo thông tin và cần xử lý logic ở mỗi lần lặp.

Lược đồ giải thuật có thể mô tả như sau:














void left_right_boundary(seq)
{
    left = 0, right = seq.size() - 1;
    while (left < right)
    {
        if ({left thỏa mãn điều kiện})	
            left += 1;
        if ({right thỏa mãn điều kiện})
            right -= 1;
		
        // Xử lý logic, có thể trước hoặc sau khi dịch chuyển hai con trỏ.
        {Xử lý logic};
    }
}

2. Bài toán ví dụ

Bài toán 1

Cho dãy số

A

gồm

n

phần tử

a_{1}, a_{2}, \dots, a_{n}

đã được sắp xếp theo thứ tự tăng dần.

Yêu cầu: Đếm số cặp phần tử

(a_{i}, a_{j})

thỏa mãn

a_{i} + a_{j} = k

với

k

là số nguyên cho trước? Lưu ý, hai cặp số là hoán vị của nhau thì chỉ tính một lần.

Input:

Dòng đầu tiên chứa hai số nguyên dương
$n$ và
$k$ .
Dòng thứ hai chứa
$n$ số nguyên dương
$a_{1}, a_{2}, \dots, a_{n}$ phân tách nhau bởi dấu cách.

Ràng buộc:

$1 \leq n \leq 10^{7}$ .
$1 \leq k \leq 10^{9}$ .
$1 \leq a_{i} \leq 10^{9}; \forall i : 1 \leq i \leq n$ .

Output:

In ra số lượng cặp số tìm được.

Sample Input:

7 15
1 3 5 7 8 9 10

Sample Output:

Ý tưởng

Phương án hai vòng lặp cho bài toán này quá đơn giản nên tôi sẽ không nhắc đến nữa.

Một phương án khác mà các bạn học sinh thường nghĩ đến cho bài toán này sẽ là duyệt mọi

a_{i}

và tìm kiếm nhị phân số lượng giá trị

a_{j} = k - a_{i}

trong dãy số. Tuy nhiên, với giới hạn

n \leq 10^{7},

thì giải thuật

O (n . \log (n))

vẫn sẽ bị quá thời gian chạy 1s. Ta cần giải thuật tốt hơn, đó chính là two - pointers.

Sử dụng con trỏ

left

đặt ở đầu dãy số, và con trỏ

right

đặt ở cuối dãy số. Do dãy số đã sắp xếp tăng dần, nên ở mỗi bước lặp, ta xử lý logic như sau:

Nếu tổng
$a_{left} + a_{right} < k$ thì tăng
$left$ lên một đơn vị.
Nếu tổng
$a_{left} + a_{right} = k$ thì tăng kết quả lên một đơn vị.
Nếu tổng
$a_{left} + a_{right} > k$ thì giảm
$right$ đi một đơn vị.

Quá trình lặp sẽ kết thúc khi

left

và

right

chạm vào nhau. Lúc này ta có được giải thuật với độ phức tạp chỉ là

O (n)

Cài đặt



























#include <bits/stdc++.h>

using namespace std;

main()
{
    int n, k;
    cin >> n >> k;
	
    vector < long long > a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
	
    int res = 0;
    int left = 1, right = n;
    while (left < right)
    {
        if (a[left] + a[right] == k)
            ++res, ++left, --right;
        else if (a[left] + a[right] < k)
            ++left; 
        else 
            --right;
    }
	
    cout << res;
}

Bài toán 2

Một hàng rào gồm

n

thanh rào có độ cao lần lượt là

h_{1}, h_{2}, \dots, h_{n};

khoảng cách giữa các thanh rào với nhau bằng chính xác một đơn vị. Người ta muốn cải tạo hàng rào bằng cách chọn ra hai thanh rào bất kỳ, rồi căng một bức tranh lên đó. Bức tranh có diện tích càng lớn thì hàng rào sẽ càng trở nên đẹp mắt. Biết rằng, nếu căng một bức tranh lên hai thanh rào

(i, j)

thì chiều cao và chiều dài của bức tranh đó sẽ lần lượt là:

min (h_{i}, h_{j})

và

j - i

Yêu cầu: Tìm ra diện tích lớn nhất có thể của bức tranh căng lên?

Input:

Dòng đầu tiên chứa số nguyên dương
$n$ .
Dòng thứ hai chứa
$n$ số nguyên dương
$h_{1}, h_{2}, \dots, h_{n}$ phân tách nhau bởi dấu cách.

Ràng buộc:

$2 \leq n \leq 10^{5}$ .
$1 \leq h_{i} \leq 10^{4}; \forall i : 1 \leq i \leq n$ .

Output:

In ra diện tích lớn nhất có thể của bức tranh căng lên.

Sample Input:

9
1 8 6 2 5 4 8 3 7

Sample Output:

Ý tưởng

Ta sử dụng hai con trỏ để kiểm soát hai thanh rào ở mỗi bước lặp. Ban đầu coi

left = 1, right = n

và diện tích lớn nhất mặc định sẽ là giữa hai thanh rào thứ

1

và thứ

n

Ở mỗi lần lặp, ta sẽ lựa chọn xem chiều cao của bức tranh tạo ra sẽ là

left

hay

right

(bên nào thấp hơn sẽ được chọn). Sau đó, dịch chuyển con trỏ ở bên tương ứng cho tới khi thu được một thanh rào có chiều cao lớn hơn chiều cao đã chọn, để loại bỏ trước những phương án không tốt hơn kết quả hiện tại.

Kết thúc mỗi bước lặp ta cập nhật diện tích bức tranh lớn nhất vào một biến

max\_area

Độ phức tạp:

O (n)

Cài đặt
















































#include <bits/stdc++.h>

using namespace std;

void solution(vector < int > &height)
{
    int left = 0, right = height.size() - 1;
    int max_area = (right - left) * min(height[left], height[right]);

    while (left < right)
    {
        // Chiều cao nhỏ hơn sẽ quyết định chiều cao bức tranh.
        if (height[left] <= height[right])
        {
            last_height = height[left];

            while (height[left] <= last_height && left < right)
                ++left;
        }
        else 
        {
            last_height = height[right];
            while (height[right] <= last_height && left < right)
                --right;
        }

        if (left >= right)
            return max_area;

        max_area = max(max_area, (right - left) * min(height[right], height[left]));
    }

    return max_area;
}

main()
{
    int n;
    cin >> n;

    vector < int > height(n);
    for (int i = 0; i < n; ++i)
        cin >> height[i];

    cout << solution(height);

    return 0;
}

IV. Dạng Sliding Window

1. Giải thuật tổng quát

Kĩ thuật Sliding Window là một kĩ thuật khá thú vị, nó có thể được áp dụng vào những bài toán điển hình. Ý tưởng của kĩ thuật này khá giống với kĩ thuật slow & fast, khi chúng ta sử dụng hai con trỏ liên tục tịnh tiến về phía sau, tuy nhiên điểm đáng lưu ý là kết quả của bài toán sẽ liên tục được cập nhật dựa vào đoạn con được kiểm soát bởi hai con trỏ đó.

Hãy tưởng tượng rằng ta có một chiếc xe bus với độ dài cố định,

start

và

end

lần lượt là điểm đầu và điểm cuối của xe. "Chiếc xe" này sẽ liên tục di chuyển trên dãy số cho tới khi hết dãy. Trong quá trình "trượt" trên dãy số, ta sẽ xử lý logic và cập nhật kết quả cần thiết của bài toán.

Mô hình thuật toán có thể mô tả như sau:












void sliding_window(seq)
{
    // Xác định kích thước của đoạn trượt: window_size
    start = 0, end = start + window_size - 1;

    while (end < seq.size())
    {
        {Tính toán kết quả của window hiện tại};
        {Dịch chuyển window ra phía sau};
        {Cập nhật kết quả tốt nhất};
    }
}

Các bước cần làm trong kĩ thuật Sliding Window có thể tóm tắt như sau:

Xác định kích thước của "window" - tức là khoảng cách giữa hai con trỏ. Kích thước này có thể là cố định hoặc không cố định, tùy vào bài toán.
Tính toán kết quả cho "window" thứ nhất (tức là tính từ vị trí
$start$ của đoạn hiện tại).
Sử dụng vòng lặp để tịnh tiến "window" ra phía sau một đơn vị, rồi tiếp tục tính toán kết quả trên "window" mới.

Kĩ thuật Sliding Window rất hữu ích trong các bài toán liên quan tới kết quả lớn nhất/nhỏ nhất trên các đoạn cố định của dãy số hoặc chuỗi kí tự. Sau đây chúng ta sẽ cùng xem xét một số ví dụ tiêu biểu của kĩ thuật này.

2. Bài toán ví dụ

Bài toán 1

Cho trước dãy số

A

gồm

n

phần tử

a_{1}, a_{2}, \dots, a_{n}

và một số nguyên dương

k

Yêu cầu: Hãy xác định đoạn con có kích thước bằng

k

có tổng lớn nhất?

Input:

Dòng đầu tiên chứa hai số nguyên dương
$n$ và
$k$ .
Dòng thứ hai chứa
$n$ số nguyên
$a_{1}, a_{2}, \dots, a_{n}$ phân tách bởi dấu cách.

Ràng buộc:

$1 \leq k \leq n \leq 10^{5}$ .
$| a_{i} | \leq 10^{9}; \forall i : 1 \leq i \leq n$ .

Output:

In ra tổng của đoạn con tìm được.

Sample Input:

9 4
1 4 2 10 2 3 1 0 20

Sample Output:

Ý tưởng

Dễ thấy, do các đoạn con ta cần xét có kích thước cố định bằng

k

nên kích thước của window sẽ chính bằng

k

Nếu như xét mọi đoạn con độ dài

k

bằng hai vòng lặp thì chắc chắn sẽ bị quá thời gian, do

n \leq 10^{5}

Ta xét liên tục các đoạn con độ dài

k

bằng cách sử dụng sliding window như sau: Gọi

window\_sum

là tổng của đoạn con đang xét. Nhận thấy, mỗi khi tịnh tiến window ra phía sau một đơn vị, giả sử nó kết thúc tại vị trí

i

thì tổng đoạn con sẽ thay đổi một lượng là:

window\_sum = window\_sum + a_{i} - a_{i - k}

Vì thế, ta chỉ cần sử dụng một vòng lặp để liên tục cập nhật tổng đoạn con lớn nhất.

Độ phức tạp:

O (n)

Cài đặt
























#include <bits/stdc++.h>
#define int long long

using namespace std;

main()
{
    int n, k;
    cin >> n >> k;

    vector < int > a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int res = accumulate(a.begin() + 1, a.begin() + k + 1, 0);
    int window_sum = res;
    for (int i = k + 1; i <= n; ++i)
    {
        window_sum += (a[i] - a[i - k]);
        res = max(res, window_sum);
    }

    cout << res;
}

Bài toán 2

Cho trước một dãy số

A

gồm

n

số nguyên là các bit

0

và

1

cùng với một số nguyên dương

k

Yêu cầu: Hãy tìm một tập gồm nhiều nhất các đoạn con của dãy

A

sao cho kích thước của các đoạn con đó đều đôi một khác nhau, và tổng của các đoạn con đều bằng

k ?

Input:

Dòng đầu tiên chứa hai số nguyên dương
$n$ và
$k$ .
Dòng thứ hai chứa một dãy số gồm
$n$ số
$0$ hoặc
$1$ phân tách nhau bởi dấu cách.

Ràng buộc:

$1 \leq k \leq n \leq 10^{5}$ .

Output:

In ra kích thước lớn nhất của tập hợp các đoạn con tìm được. Nếu không tồn tại thì in ra
$0$ .

Sample Input:

4 2
0 1 1 0

Sample Output:

Giải thích:

Tập các đoạn con tìm được là:

{{0, 1, 1, 0}; {0, 1, 1}; {1, 1}}

Ý tưởng

Nhận thấy, tổng của một đoạn con chính là số lượng số

1

trong đoạn con đó. Ta sử dụng kĩ thuật sliding window như sau:

Duy trì một biến
$c o u n t$ để đếm số lượng số
$1$ trong window hiện tại.
Nếu
$c o u n t < k$ thì tăng kích thước window lên, còn ngược lại thì giảm kích thước của windown xuống.
Với các windown có
$c o u n t = k,$ ta đẩy kích thước của window đó vào một set để lưu trữ các giá trị khác nhau.
Cuối cùng, kích thước của set chính là kết quả bài toán.

Độ phức tạp:

O (n)

Cài đặt

























































#include <bits/stdc++.h>

using namespace std;

int maximum_subset(int n, vector < int > &a, int k)
{
    unordered_set < int > s;

    // Vị trí bắt đầu và tổng của window hiện tại.
    int ptr = 1;
    int window_sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        // Cập nhật tổng đoạn con kết thúc tại a[i].
        window_sum += a[i]; 

        // Nếu tổng window hiện tại < k thì tiếp tục tăng kích thước window.
        if (window_sum < k)
            continue;
        
        // Nếu tổng window hiện tại > k thì dịch vị trí xuất phát của window lên.
        if (cur_sum > k)
        {
            while (cur_sum > k)
                cur_sum -= a[ptr++];
        }

        // Nếu tổng window hiện tại = k thì lấy tất cả các đoạn con như vậy đưa vào set.
        if (cur_sum == k)
        {
            s.insert(i - ptr + 1);

            int j = ptr;
            while (a[j] == 0)
            {
                s.insert(i - t);
                ++t;
            }
        }
    }

    return s.size();
}

main()
{
    int n, k;
    cin >> n >> k;

    vector < int > a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    cout << maximum_subset(n, a, k);

    return 0;
}

I. Tổng quan về kĩ thuật Two Pointers

II. Dạng bài Slow And Fast

1. Giải thuật tổng quát

2. Bài toán ví dụ

Bài toán 1

Ý tưởng

Cài đặt

Bài toán 2

Ý tưởng

Subtask 1

Subtask 2

Cài đặt

III. Dạng Left & Right Boundary

1. Giải thuật tổng quát

2. Bài toán ví dụ

Bài toán 1

Ý tưởng

Cài đặt

Bài toán 2

Ý tưởng

Cài đặt

IV. Dạng Sliding Window

1. Giải thuật tổng quát

2. Bài toán ví dụ

Bài toán 1

Ý tưởng

Cài đặt

Bài toán 2

Ý tưởng

Cài đặt

V. Tài liệu tham khảo

Read more

Giáo án Lập trình C++ cơ bản - Định hướng thi HSG Tin học

Link ảnh

[LTTĐNC - Chủ đề 2] Cấu trúc dữ liệu NC và Các kĩ thuật tối ưu hoá 2.4: Chia căn (phần 1) - Giới thiệu về Chia căn