15. 3Sum

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/group-anagrams/description/

Table of Contents

1. Cách tiếp cận vấn đề

Có Two Sum rồi thì ta cũng sẽ có một bài dành riêng cho Three Sum 😁 Tuy nhiên bài toán sẽ yêu cầu ta tìm tất cả các bộ ba index sao cho tổng của các phần tử ở 3 ô index đó bằng 0. Lưu ý là tìm tất cả bộ ba chứ không phải chỉ tìm 1 bộ duy nhất, và các bộ này phải là duy nhất. Ví dụ: (1,2,3) với (3,2,1) được tính là một mà thôi vì vậy ta chỉ cần trả về một trong hai.

Về idea thì nếu ta sử dụng BruteForce chắc chắn sẽ bị Timeout, do ngoài việc sử dụng 3 vòng for để tính tổng của các phần tử, ta cũng cần phải so sánh và loại bỏ đi những bộ ba đã tồn tại trước đó. Chắc chắn là rất khó để đạt được O(n) về mặt thời gian vì ta không thể tính toán được hết tất cả các bộ số bằng cách chỉ duyệt qua các phần tử 1 lần được.

Ta có thể quy bài toán giống như bài Two Sum: Tìm vị trí của 2 số sao cho target của nó bằng 0. Mà để cộng lại bằng 0 thì 2 số đó phải là đối số của nhau, 1 số là num thì số còn lại phải là -num. Áp dụng cho bài toán Three Sum này:

• Ta cần tìm 1 số âm nào đó -num - Cần 1 pointer để giữ số âm này
• Và cần tìm 1 số dương num là đối số của nó, từ số nguyên dương này ta lại tách ra giống bài Two Sum:
• Ta cần tìm 2 số sao cho tổng của chúng bằng target là num - Cần sử dụng 2 pointers để giải quyết sub-problem này

Vậy tổng cộng ta sẽ có 3 con trỏ, nên mình tạm gọi kỹ thuật này là 3 pointers, từ idea này ta sẽ hoàn thiện thêm một số bước để có thể đảm bảo các bộ số trả về là duy nhất và không trùng nhau.

2. Solution & Phân Tích

Đầu tiên để áp dụng được idea đã nêu, ta cần biến dãy input đã cho trở nên đơn điệu, hay nói cách khác ta cần sắp xếp lại dãy theo thứ tự tăng dần và nó sẽ tốn O(nlogn) time-complexity. Việc sắp xếp này vô cùng hữu ích vì nó còn giúp ta gom lại được những phần tử giống nhau sẽ nằm liền kề. Và nó cũng không làm sai kết quả của bài toán khi nó yêu cầu ta trả về bộ ba giá trị thay vì index. Sau khi sắp xếp xong:

• Ta sẽ dùng 1 con trỏ i di chuyển từ đầu mảng về tới vị trí index = n - 2 thì sẽ dừng (để dành chỗ cho 2 phần tử còn lại).
• Con trỏ này chỉ trỏ về những số nhỏ hơn hoặc bằng 0, nếu nó trỏ về 1 số dương nào đó thì ta sẽ kết thúc chương trình ngay lập tức vì 3 số dương không thể có tổng bằng 0 được.
• Hoặc nếu ta phát hiện phần tử hiện tại trùng với phần tử trước đó thì ta sẽ bỏ qua phần tử đó và xét tới phần tử kết tiếp.
• Tiếp theo với mỗi vị trí của con trỏ i, ta sẽ sử dụng kỹ thuật 2 Pointers để tìm ra vị trí của 2 phần tử có sum bằng số nguyên dương sao cho khi cộng với giá trị tại i ta được sum = 0:
• Con trỏ left sẽ di chuyển từ i + 1 (ngay bên phải con trỏ ban đầu) cho đến khi gặp con trỏ right thì dừng lại. Tương tự con trỏ right sẽ di chuyển từ cuối mảng cho đến khi gặp con trỏ left.
• Ta sẽ tính sum tại 3 pointers: i, left và right
• Nếu sum > 0, ta cần giảm con trỏ right đi 1 đơn vị và tiếp tục tính toán
• Nếu sum < 0, ta cần tăng con trỏ left lên 1 đơn vị và tiếp tục tính toán
• Nếu sum = 0, ta ghi nhận lại bộ ba giá trị lần lượt tại các index i, left và right, sau đó để bỏ đi những phần tử trùng lặp, ta cần:
• Tăng con trỏ left cho đến khi tìm được phần tử khác với phần tử tại left hiện tại hoặc khi left = right thì dừng lại.
• Giảm con trỏ right cho đến khi tìm được phần tử khác với phần tử right hiện tại hoặc khi right = left thì dừng lại.
• Lúc này 2 con trỏ left và right đã trỏ vào các phần tử mới hoàn toàn nên ta không sợ bị trùng lặp bộ ba giá trị nữa.

Time-Complexity: O(n^2)

Space-Complexity: O(1)

Với n là số lượng các phần tử trong mảng input.

3. Code