Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/two-sum/description/
Table of Contents
1. Cách tiếp cận vấn đề
Output cần tìm là 2 vị trí index trong mảng sao cho tổng của chúng bằng với "target". Và bài toán cũng cam kết sẽ luôn luôn có 1 đáp án hợp lệ, chứ không có trường hợp không tìm thấy được 2 index nào.
Cách tiếp cận thường thấy là Bruteforce sử dụng 2 vòng for để tìm ra vị trí cần tìm. Tuy nhiên nhược điểm của cách này là độ phức tạp khá lớn O(n^2).
Để khắc phục điều đó, ta cần sử dụng thêm bộ nhớ ngoài và hướng bài toán đến việc sử dụng 1 vòng for duy nhất. Có nghĩa là tại mỗi lần duyệt ta sẽ có thể kiểm tra được phần tử hiện tại a có liên hệ gì với một trong các phần tử trước đó tạm gọi là b hay không, tổng của chúng có thể bằng target được hay không.
Hay nói cách khác thì: a + b = target => a = target - b => số a đang xét hiện tại có xuất hiện như là phần bù đối với các số b trước đó sao cho tổng chúng bằng target hay không? để giải đáp được điều này, ta cần lưu target - b lại mỗi khi ta duyệt qua số b bất kỳ trước đó, sau đó khi duyệt các số sau đó gọi là a, ta chỉ cần kiểm xem có phần bù nào bằng a không là được.
2. Solution & Phân Tích
2.1. Bruteforce
Như đã đề cập ở trên, ta sẽ sử dụng 2 vòng for:
- Vòng for thứ nhất duyệt qua các phần tử với vị trí lần lượt là i
- Vòng for thứ hai duyệt qua các phần tử ở phía sau i, tạm gọi là j
- Tại mỗi lần duyệt ta sẽ kiểm tra xem tổng 2 phần tử tại i và j có bằng target hay không, nếu có thì ta sẽ trả về 1 array có 2 phần tử là i và j (tương ứng vị trí của 2 phần tử có tổng bằng target)
Sau cùng nếu không tìm thấy ta sẽ trả về mảng rỗng, trường hợp này sẽ không xảy ra do bài toán luôn đảm bảo có duy nhất 1 đáp án hợp lệ, tuy nhiên đó là ràng buộc của bài toán, còn khi viết hàm ta vẫn cần phải trả về kết quả mặc định cho hàm khi kết quả không được trả về trong 2 vòng for.
Space Complexity: O(1) - không sử dụng thêm bộ nhớ ngoài
Time Complexity: O(n^2) - sử dụng 2 vòng for lồng nhau
n: số lượng phần tử trong mảng input nums
2.2. Sử dụng Map lưu phần bù
Ta sẽ sử dụng map với key là phần bù của số đang xét và value là vị trí của số đang xét. Hay nói cách khác, số đang xét muốn gửi gắm phần bù và vị trí của mình cho những số chuẩn bị được xét với thông điệp rằng: nếu bạn là phần bù của tôi, thì hãy lấy ra vị trí của tôi kết hợp với vị trí của bạn. 😂
Cụ thể ta sẽ sử dụng 1 vòng lặp for, mỗi khi ta duyệt qua 1 số num ở vị trí i, ta sẽ kiểm tra xem số num này có là phần bù của các số trước đó hay chưa bằng việc kiểm tra xem có tồn tại num trong map hay chưa:
- Nếu đã tồn tại, ta lấy value từ map, value này chính là vị trí của số tạo ra phần bù num tạm gọi là j, lúc này ta sẽ trả về mảng gồm 2 phần tử i và j, kết thúc hàm.
- Nếu chưa tồn tại, ta sẽ gửi gắm phần bù của num và vị trí của num vào map với key là target - num, value chính là i.
Sau cùng trả về giá trị default là mảng rỗng nếu không tìm thấy bất kỳ 2 vị trí nào tạo ra tổng bằng target (1 lần nữa, bài toán cam kết không có điều này xảy ra nhưng chúng ta cần phải pass qua được trình biên dịch)
Space Complexity: O(n) - sử dụng thêm map
Time Complexity: O(n) - sử dụng 1 vòng for
n: số lượng phần tử trong mảng input nums
3. Code
Mình sẽ demo cách dùng map vì nó tối ưu hơn về mặt thời gian so với cách làm vét cạn.
