Two Pointers và Sliding Window: Kỹ thuật tối ưu mảng và chuỗi

1. Tổng quan

Khi gặp bài toán duyệt mảng hoặc chuỗi mà giải pháp brute-force chạy O(n²) hoặc O(n³), hai kỹ thuật two pointers và sliding window thường giúp bạn đưa độ phức tạp xuống O(n). Bài này giải thích ý tưởng cốt lõi của từng kỹ thuật, kèm ví dụ Java cụ thể: two sum trên mảng đã sắp xếp, kiểm tra palindrome, tổng con lớn nhất trong window cố định, và substring dài nhất không lặp ký tự. Đọc xong, bạn sẽ nhận ra pattern và áp dụng được cho nhiều bài toán tương tự.

2. Two Pointers là gì

Two pointers là kỹ thuật dùng hai biến chỉ số (con trỏ) di chuyển trên một cấu trúc dữ liệu (thường là mảng hoặc chuỗi đã sắp xếp) để tránh việc duyệt lồng nhau. Hai con trỏ có thể di chuyển:

• Cùng chiều (fast/slow): dùng cho loại bỏ phần tử trùng, phát hiện cycle.
• Ngược chiều (left/right từ hai đầu): dùng cho tìm cặp tổng bằng target, kiểm tra palindrome.

2.1. Two pointers ngược chiều: tìm cặp có tổng bằng target

Bài toán kinh điển: cho mảng đã sắp xếp tăng, tìm hai số có tổng bằng target.

public class TwoSumSorted {

    public int[] findPair(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{numbers[left], numbers[right]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

Giải thích:

• left bắt đầu từ đầu mảng, right từ cuối mảng.
• Nếu sum < target, số bên left quá nhỏ nên tăng left để lấy số lớn hơn.
• Nếu sum > target, số bên right quá lớn nên giảm right.
• Vòng lặp chạy tối đa n bước vì mỗi lần left hoặc right dịch một ô, cho độ phức tạp O(n) thay vì O(n²) của cách duyệt hai lớp.

Test với JUnit 5 + AssertJ:

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.10.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.25.3</version>
    <scope>test</scope>
</dependency>

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class TwoSumSortedTest {

    private final TwoSumSorted twoSum = new TwoSumSorted();

    @Test
    void shouldFindPairWhenSumMatchesTarget() {
        int[] numbers = {1, 3, 5, 8, 11};

        int[] result = twoSum.findPair(numbers, 13);

        assertThat(result).containsExactly(5, 8);
    }
}

Lưu ý: kỹ thuật này yêu cầu mảng đã sắp xếp. Nếu mảng chưa sắp xếp, bạn phải sort trước (O(n log n)) hoặc dùng HashMap để giữ O(n) mà không cần sort.

2.2. Two pointers để kiểm tra palindrome

public class PalindromeChecker {

    public boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Hai con trỏ xuất phát từ hai đầu chuỗi, so sánh ký tự rồi tiến vào giữa. Nếu gặp cặp ký tự khác nhau, trả về false ngay — không cần duyệt hết. Đây là lý do kỹ thuật này nhanh hơn việc đảo chuỗi rồi so sánh (reverse().equals()), vì tránh được việc tạo object StringBuilder trung gian.

3. Sliding Window là gì

Sliding window là biến thể của two pointers, áp dụng cho bài toán liên quan đến dãy con liên tiếp (subarray/substring). Thay vì tính lại từ đầu cho mỗi vị trí bắt đầu, bạn giữ một “cửa sổ” [left, right] và cập nhật dần khi cửa sổ trượt, tái sử dụng kết quả tính trước đó.

Có hai loại:

• Fixed-size window: kích thước cửa sổ cố định (ví dụ k phần tử).
• Variable-size window: kích thước co giãn theo điều kiện bài toán.

3.1. Fixed-size window: tổng con lớn nhất kích thước k

public class MaxSumSubarray {

    public int maxSum(int[] numbers, int windowSize) {
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }

        int maxSum = windowSum;
        for (int right = windowSize; right < numbers.length; right++) {
            windowSum += numbers[right] - numbers[right - windowSize];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

Giải thích:

• Vòng lặp đầu tính tổng của cửa sổ đầu tiên (từ index 0 đến windowSize - 1).
• Từ đó, mỗi lần dịch cửa sổ sang phải một bước: cộng phần tử mới vào (numbers[right]), trừ phần tử vừa ra khỏi cửa sổ (numbers[right - windowSize]).
• Nhờ vậy, mỗi bước chỉ tốn O(1) thay vì tính lại tổng O(k), tổng độ phức tạp là O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class MaxSumSubarrayTest {

    private final MaxSumSubarray solver = new MaxSumSubarray();

    @Test
    void shouldReturnMaxSumOfWindowSizeThree() {
        int[] numbers = {2, 1, 5, 1, 3, 2};

        int result = solver.maxSum(numbers, 3);

        assertThat(result).isEqualTo(9); // cửa sổ [5, 1, 3]
    }
}

3.2. Variable-size window: substring dài nhất không lặp ký tự

Bài này cửa sổ co giãn tùy điều kiện “không có ký tự lặp”.

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public int lengthOfLongestSubstring(String text) {
        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < text.length(); right++) {
            char current = text.charAt(right);
            if (lastSeenIndex.containsKey(current) && lastSeenIndex.get(current) >= left) {
                left = lastSeenIndex.get(current) + 1;
            }
            lastSeenIndex.put(current, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

Giải thích:

• right luôn tiến tới (mở rộng cửa sổ), left chỉ nhảy khi gặp ký tự trùng bên trong cửa sổ hiện tại.
• lastSeenIndex lưu vị trí xuất hiện gần nhất của mỗi ký tự để biết left cần nhảy tới đâu.
• Điều kiện lastSeenIndex.get(current) >= left đảm bảo chỉ coi là “trùng” nếu ký tự đó còn nằm trong cửa sổ hiện tại, tránh nhảy left lùi lại sai hướng.
• Mỗi ký tự được xử lý đúng một lần ở right, nên tổng độ phức tạp là O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class LongestUniqueSubstringTest {

    private final LongestUniqueSubstring solver = new LongestUniqueSubstring();

    @Test
    void shouldReturnLengthOfLongestUniqueSubstring() {
        int result = solver.lengthOfLongestSubstring("abcabcbb");

        assertThat(result).isEqualTo(3); // "abc"
    }

    @Test
    void shouldHandleAllSameCharacters() {
        int result = solver.lengthOfLongestSubstring("bbbbb");

        assertThat(result).isEqualTo(1);
    }
}

Đầu ra khi debug thủ công với "abcabcbb":

right=0 'a' -> window="a"    length=1
right=1 'b' -> window="ab"   length=2
right=2 'c' -> window="abc"  length=3
right=3 'a' -> trùng, left=1 -> window="bca" length=3
right=4 'b' -> trùng, left=2 -> window="cab" length=3
...
maxLength = 3

4. So sánh và khi nào dùng kỹ thuật nào

Tình huống	Kỹ thuật phù hợp
Mảng đã sắp xếp, tìm cặp/tam giác thỏa điều kiện tổng	Two pointers ngược chiều
Kiểm tra tính đối xứng (palindrome), đảo mảng in-place	Two pointers ngược chiều
Loại bỏ phần tử trùng trong mảng đã sắp xếp	Two pointers cùng chiều (fast/slow)
Subarray/substring có kích thước cố định k	Sliding window fixed-size
Subarray/substring thỏa điều kiện động (không lặp, tổng ≤ target…)	Sliding window variable-size

Điểm chung: cả hai kỹ thuật đều tránh tính toán lại phần đã xử lý, chuyển từ O(n²) xuống O(n) bằng cách duy trì trạng thái (sum, set, map) khi con trỏ/cửa sổ di chuyển.

5. Lỗi thường gặp

• Quên điều kiện dừng left < right: dễ gây vòng lặp vô hạn hoặc so sánh một phần tử với chính nó khi left == right.
• Áp dụng two pointers cho mảng chưa sắp xếp mà quên sort trước — kết quả sai hoàn toàn vì logic tăng/giảm con trỏ dựa trên tính đơn điệu của mảng.
• Trong sliding window, quên cập nhật trạng thái khi left dịch: ví dụ quên xóa phần tử cũ khỏi HashMap/sum, dẫn đến cửa sổ “nhớ” dữ liệu đã không còn thuộc cửa sổ.
• Nhầm điều kiện mở rộng/co hẹp cửa sổ: với variable-size window, cần xác định rõ điều kiện nào làm right tiến, điều kiện nào làm left tiến — nếu đảo ngược, window sẽ không bao giờ co lại đúng.

Lưu ý: hai kỹ thuật này không phù hợp khi bài toán yêu cầu xét mọi tổ hợp con không liên tiếp (ví dụ subset sum) — lúc đó cần backtracking hoặc dynamic programming, không phải sliding window.

6. Kết luận

Two pointers và sliding window là hai công cụ nền tảng để giải bài toán mảng/chuỗi với độ phức tạp tuyến tính. Nhận diện được pattern — mảng đã sắp xếp cần tìm cặp, hay subarray/substring liên tiếp cần tối ưu — giúp bạn chọn đúng kỹ thuật và viết code ngắn, dễ test như các ví dụ trên. Khi luyện tập, hãy thử tự vẽ lại trạng thái left/right qua từng bước để hiểu rõ invariant trước khi code.