Login

Hai con trỏ và cửa sổ trượt: hai mẫu giải bài giúp tiết kiệm thời gian phỏng vấn

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Trong các buổi phỏng vấn thuật toán, rất nhiều bài thực chất là biến thể của vài mẫu quen thuộc. Học mẫu giúp bạn nhận ra hướng giải nhanh thay vì mò từ đầu. Bài này giới thiệu hai mẫu phổ biến: hai con trỏ và cửa sổ trượt, kèm ví dụ và dấu hiệu nhận biết.

Mẫu 1: Hai con trỏ (Two Pointers)

Dùng hai chỉ số cùng di chuyển trên mảng hoặc chuỗi, thường là từ hai đầu tiến vào giữa hoặc cùng đi theo một chiều với tốc độ khác nhau. Mục tiêu là thay vòng lặp lồng nhau O(n²) bằng một lượt duyệt O(n).

Dấu hiệu nhận biết

  • Mảng đã sắp xếp hoặc có thể sắp xếp mà không mất ý nghĩa bài toán.
  • Bài yêu cầu tìm cặp, bộ ba có tính chất nào đó (tổng, hiệu).
  • Bài về chuỗi đối xứng hoặc đảo ngược tại chỗ.
  • Bài loại bỏ hoặc gộp phần tử trong mảng tại chỗ.

Ví dụ: hai số có tổng bằng target trong mảng đã sắp xếp

function twoSumSorted(nums, target) {  let left = 0;  let right = nums.length - 1;  while (left < right) {    const sum = nums[left] + nums[right];    if (sum === target) return [left, right];    if (sum < target) left++;    else right--;  }  return null;}console.log(twoSumSorted([1, 3, 4, 6, 9], 10)); // [0, 4]

Vì mảng đã sắp xếp, nếu tổng nhỏ hơn mục tiêu thì cần số lớn hơn nên tăng left; nếu lớn hơn thì giảm right. Mỗi bước loại bỏ ít nhất một ứng viên nên tổng cộng O(n) thời gian và O(1) bộ nhớ.

Ví dụ: xóa phần tử trùng trong mảng đã sắp xếp (tại chỗ)

function removeDuplicates(nums) {  if (nums.length === 0) return 0;  let write = 1;  for (let read = 1; read < nums.length; read++) {    if (nums[read] !== nums[read - 1]) {      nums[write] = nums[read];      write++;    }  }  return write; // số phần tử khác nhau}

Con trỏ read quét toàn bộ mảng còn write đánh dấu vị trí ghi tiếp theo. Đây là biến thể hai con trỏ cùng chiều (còn gọi là nhanh và chậm).

Mẫu 2: Cửa sổ trượt (Sliding Window)

Duy trì một đoạn liên tiếp (cửa sổ) của mảng hoặc chuỗi, mở rộng bên phải và thu hẹp bên trái, thay vì tính lại toàn bộ đoạn mỗi lần.

Dấu hiệu nhận biết

  • Bài hỏi về đoạn con hoặc chuỗi con liên tiếp.
  • Cần tìm đoạn dài nhất, ngắn nhất hoặc tổng lớn nhất thỏa một điều kiện.
  • Có từ khóa như "k phần tử liên tiếp", "không lặp lại", "tối đa".

Ví dụ: tổng lớn nhất của k phần tử liên tiếp

function maxSumK(nums, k) {  if (nums.length < k) return null;  let sum = 0;  for (let i = 0; i < k; i++) sum += nums[i];  let best = sum;  for (let i = k; i < nums.length; i++) {    sum += nums[i] - nums[i - k];    best = Math.max(best, sum);  }  return best;}console.log(maxSumK([2, 1, 5, 1, 3, 2], 3)); // 9

Thay vì cộng lại k số mỗi lần (O(n·k)), ta cộng số mới vào và trừ số vừa rời cửa sổ, nên chỉ O(n).

Ví dụ: chuỗi con dài nhất không có ký tự lặp

function longestUnique(s) {  const seen = new Set();  let left = 0;  let best = 0;  for (let right = 0; right < s.length; right++) {    while (seen.has(s[right])) {      seen.delete(s[left]);      left++;    }    seen.add(s[right]);    best = Math.max(best, right - left + 1);  }  return best;}console.log(longestUnique('abcabcbb')); // 3

Cửa sổ [left, right] luôn không chứa ký tự trùng. Khi gặp ký tự trùng, ta thu hẹp bên trái cho đến khi hợp lệ. Mỗi ký tự được thêm và xóa tối đa một lần nên độ phức tạp là O(n).

Cách chọn nhanh giữa hai mẫu

Tình huốngMẫu gợi ý
Tìm cặp trong mảng đã sắp xếpHai con trỏ hai đầu
Kiểm tra đối xứngHai con trỏ hai đầu
Đoạn con liên tiếp có điều kiệnCửa sổ trượt
Sửa mảng tại chỗHai con trỏ cùng chiều

Lưu ý khi áp dụng

  • Hai con trỏ hai đầu chỉ đúng khi dữ liệu có thứ tự hoặc có tính chất đơn điệu.
  • Cửa sổ trượt cho số âm cần cẩn thận vì tổng không còn đơn điệu khi mở rộng cửa sổ.
  • Luôn kiểm tra mảng rỗng, một phần tử và k lớn hơn độ dài mảng.

Kết luận

Nhận ra mẫu là kỹ năng luyện được. Hãy giải khoảng năm đến mười bài cho mỗi mẫu, và sau mỗi bài ghi lại dấu hiệu giúp bạn nhận ra mẫu đó. Sau một thời gian, bạn sẽ thấy các bài lạ trở nên quen thuộc hơn nhiều.

Nếu bạn muốn học thuật toán theo lộ trình có bài tập, hãy xem thêm các khóa học tại codebem.com.

author_photo
Nguyễn Đình Cường

0 comment