### Phân tích bài toán
Chúng ta cần tìm $3$ chỉ số phân biệt $i, j, k$ sao cho $a_i + a_j + a_k = x$.
Nếu ta cố định một chỉ số, giả sử là $i$, bài toán sẽ trở thành: Tìm hai chỉ số $j$ và $k$ (với $j, k \neq i$) sao cho:
$$a_j + a_k = x - a_i$$
Lúc này, bài toán quy về dạng bài toán kinh điển [Số Cặp](https://marisaoj.com/problem/100) (Tìm hai số có tổng bằng một giá trị xác định).
### Ý tưởng
Để giải quyết bài toán hiệu quả, ta có thể thực hiện các bước sau:
1. **Lưu vết chỉ số:** Vì bài toán yêu cầu xuất ra chỉ số ban đầu nhưng thuật toán tối ưu lại cần thay đổi vị trí các phần tử, ta cần lưu trữ mảng $a$ dưới dạng các cặp giá trị `(giá trị, chỉ số ban đầu)`.
2. **Sắp xếp:** Sắp xếp mảng theo thứ tự tăng dần về mặt giá trị. Việc này cho phép sử dụng kỹ thuật Hai con trỏ.
3. **Duyệt và tìm kiếm:**
* Duyệt chỉ số $i$ từ $1$ đến $n-2$ để cố định phần tử thứ nhất.
* Với mỗi $i$, ta đặt mục tiêu tìm tổng còn thiếu là $target = x - a_i$.
* Sử dụng hai con trỏ, đặt $j = i + 1$ (phần tử ngay sau $i$) và $k = n$ (phần tử cuối mảng).
* Trong khi $j < k$:
* Nếu $a_j + a_k = target$: Ta đã tìm thấy bộ ba thỏa mãn. Ghi nhận chỉ số ban đầu của $a_i, a_j, a_k$ và kết thúc.
* Nếu $a_j + a_k < target$: Tổng hiện tại nhỏ hơn mong muốn, ta cần tăng tổng lên bằng cách tăng $j$ (dịch chuyển sang phải).
* Nếu $a_j + a_k > target$: Tổng hiện tại lớn hơn mong muốn, ta cần giảm tổng xuống bằng cách giảm $k$ (dịch chuyển sang trái).
### Độ phức tạp
* **Thời gian:** Việc sắp xếp tốn $O(n \log n)$. Vòng lặp $i$ kết hợp với hai con trỏ $j, k$ duyệt qua mảng tốn $O(n^2)$. Tổng độ phức tạp là $O(n^2)$.
* **Không gian:** $O(n)$ để lưu trữ mảng các cặp giá trị.
abc
Created at
3 likes