- vừa được xem lúc

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

0 0 4

Người đăng: Phan Trần Hiếu Nhân

Theo Viblo Asia

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.

image.png

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

  1. 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.
  2. Kiểu bài toán nào nên được xem xét dùng kỹ thuật này.
  3. 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ỏ ij 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.

image.png

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.

image.png

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.

image.png

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;

image.png

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.

image.png

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;

image.png

Đ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)

image.png

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

  1. Container With Most Water
  2. 3-Sum
  3. Triangle Numbers
  4. Squares of a Sorted Array
  5. Reverse String
  6. Valid Palindrome
  7. Trapping Rain Water

Tham khảo

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

Bình luận

Bài viết tương tự

- vừa được xem lúc

Lập trình và tư duy thuật toán sáng tạo (Kì 2) - Tóm lược kiến thức đại số tổ hợp

Trong phần đầu Lập trình và tư duy thuật toán sáng tạo (Kì 1) Mình đã giới thiệu về khái niệm, lý do bạn cần sử dụng thuật toán và những điều cơ bản đề giải quyết một bài toán. Và giờ thì chúng ta bắt đầu tìm hiểu xem thế giới "diệu kỳ" này có gì nhé.

0 0 195

- vừa được xem lúc

Process (Máy tính) và những điều có thể chưa biết - Phần II - Multitasking

Tiếp nối phần I mình đã tìm hiểu Process như thế nào, các component của 1 Process, và cách Process hoạt động. Phần tiếp theo này chúng ta cùng xem liệu Multitasking có phải là bến đỗ hạnh phúc khi muốn optimize thời gian chạy của 1 chương trình.

0 0 5.2k

- vừa được xem lúc

Process (Máy tính) và những điều có thể chưa biết - Phần I

Chào anh em một buổi sáng đầy năng lượng. Lý do mình viết bài chia sẻ này vì có 2 vấn đề mình thấy rất nhiều bạn gặp phải.

0 0 180

- vừa được xem lúc

Tìm hiểu khái niệm Hash Table

Có lẽ khái niệm này cũng không quá xa lạ gì với các anh em Engineer và bản thân mình sau 2 năm đầu đi làm và lần đầu tiên nghe về khái niệm này cũng hiểu một cách rất là mơ hồ . Yeah và dĩ nhiên không để nỗi đau thêm dài (thật ra mình tò mò là chính) nên mình cũng tìm hiểu về cách làm việc của Hash

0 0 149

- vừa được xem lúc

Thuật toán Apriori khai phá luật kết hợp trong Data Mining

Bài toán khai thác tập phổ biến (frequent itemset) là bài toán rất quan trọng trong lĩnh vực data mining. Bài toán khai thác tập phổ biến là bài toán tìm tất cả tập các hạng mục (itemset) S có độ phổ

0 0 527

- vừa được xem lúc

Series Data structures and algorithms

Giới thiệu. Xin chào các bạn. Tổng quan. Hàng ngày, chúng ta vẫn thường xuyên sử dụng các cấu trúc dữ liệu như Array,Map.

0 0 160