Đã đăng vào khoảng 14 giờ trước 5 phút đọc

Kỹ thuật Two Pointers trong thuật toán

Intro

Bạn đang bắt đầu hành trình luyện thuật toán cho Interview hoặc chỉ đơn giản là đang luyện Leetcode, thì chắc hẳn bạn cũng đã nghe qua kỹ thuật Two Pointers. Hãy cùng mình tìm hiểu kỹ thuật này một cách ĐƠN GIẢN VÀ DỄ HIỂU nhé!

Một tí thông tin về mình, mình tên là Nhân, là Backend Engineer chuyên code với Golang và đi làm đã được 4 năm rồi. Mình cũng vật vả học và luyện thuật toán như bao người, nay mình mới đủ 1 chút tự tin chia sẻ những gì mình hiểu và học được đến mọi người, nên có gì sai xót có thể góp ý cho mình nhé, mình xin cảm ơn 😄

First thing first

Kỹ thuật này đề cập đến việc dùng 2 con trỏ để bắt đầu tại điểm đầu và cuối của một Mãng và dần dần di chuyển về phía nhau để tìm ra cặp số đáp án.

Trong bài này chúng ta sẽ tìm hiểu:

Một bài toán đơn giản để minh hoạ cho động lực phía sau kỹ thuật 2 còn trỏ này.
Kiểu bài toán nào nên được xem xét dùng kỹ thuật này.
Danh sách bài toán (có ví dụ minh hoạ) để bạn thử vận dụng dựa trên các khái niệm đã đề cập ở đây.

Bài toán: Two Sum

MÔ TẢ

Cho một mãng số đã sắp xếp nums , xác định liệu có tồn tại một cặp số nào mà tổng của nó bằng với target đầu vào đã cho.

VÍ DỤ:

Input: nums = [1,3,4,6,8,10,13], target = 13 Output: True (3 + 10 = 13) Input: nums = [1,3,4,6,8,10,13], target = 6 Output: False

Một cách giải “ngô nghê” cho bài toán này là dùng 2 con trỏ i và j trong một vòng lặp lồng nhau để kiểm tra từng cặp trong mảng, nên có O(n^2) cặp được kiểm tra

func isPairSum(nums []int, target int) bool {
	for i := 0; i < len(nums); i++{
		for j := i; j < len(nums); j++{
			if nums[i] + nums[j] == target {
				return true
			}
		}
	}
	return false
}

Tuy nhiên, dựa trên những điều kiện mà đầu vào đã cho, nếu ta suy nghĩ thêm một chút về cách chúng ta đặt con trỏ ở đâu và di chuyển chúng như thế nào, thì chúng ta có thể loại bỏ số cặp mà chúng sẽ kiểm tra xuống còn O(n). Việc hiểu lý do tại sao chúng ta có thể GIẢM THIỂU những cặp cần kiểm tra là CHÌA KHOÁ để hiểu kỹ thuật 2 con trỏ này.

Loại bỏ các cặp

Kỹ thuật 2 con trỏ tận dụng thực tế rằng MÃNG đầu vào đã được SẮP XẾP.

Hãy dùng nó để giải bài toán Two Sum này khi nums = [1, 3, 4, 6, 8, 10, 13] và target = 13.

Chúng ta bắt đầu khởi tạo 2 con trỏ ở 2 đầu của mảng, nó được coi là cặp của các con số giống như chúng ta thường làm.

Cặp đầu tiên này có tổng là 14, nó lớn hơn target là 13. Do mãng đã được sắp xếp trước đó, nên tất cả các cặp còn lại từ bên con trỏ bên PHẢI cũng sẽ luôn có tổng lớn hơn target , vì tất cả chúng lớn hơn 1, là giá trị từ bên trái.

Như là: 13 + 1 = 14; 13 + 3 = 16;

Thế nên, để di chuyển trên cặp tiếp theo, ta di chuyển con trỏ bên PHẢI về lại, để loại bỏ những cặp không cần thiết khỏi tìm kiếm.

Và bây giờ, bởi vì tổng nhỏ hơn target , nên ta biết chắc chắn rằng tất cả các cặp còn lại ở phía con trỏ bên TRÁI luôn có tổng nhỏ hơn target . Vậy nên, ta cần di chuyển con trỏ bên TRÁI để có thể loại bỏ những cặp không cần thiết.

Như là: 10 + 1 = 11 < 13;

Điều này tiếp tục cho đến khi thấy cặp phù hợp hoạc 2 con trỏ gặp được nhau (left == right ⇒ stop)

func twoSum(nums []int, target int) bool{
	left, right := 0, len(nums)-1
	for left < right {
		sum := nums[left] + nums[right]
		if sum == target {
			return true
		} else if sum < target {
			left++
		}else {
			right--
		}
	}
	return false
}

Tóm lại

Kỹ thuật Two-pointer này tận dụng mãng đầu đã được sắp xếp để giảm bớt số cặp chúng ta cần kiểm tra từ O(n^2) xuống còn O(n) .
2 con trỏ được bắt đầu tại 2 điểm đầu và cuối của mảng, cũng như đại diện cho 1 cặp số để ta xem xét.
Chúng lặp lại việc so sánh và duy chuyển lại gần nhau sao cho giảm thiểu những lần kiểm tra không cần thiết, cho đến khi tìm được cặp đáp ứng tiêu chí hoặc cho đến khi gặp nhau (trường hợp không tìm thấy).

LUYỆN TẬP

Tham khảo

https://www.hellointerview.com/learn/code/two-pointers/overview