Hướng giải: Tổng bộ ba

Nguồn: CSES

Giả sử ta biết giá trị ở vị trí ngoài cùng bên trái trong tổng là $a_i$ ~a_i~. Khi đó, bài toán còn lại là tìm hai giá trị khác nhau trong đoạn con $a_{i+1}...a_n$ ~a_{i+1}...a_n~ có tổng bằng $x - a_i$ ~x - a_i~. Đây là một bài toán đơn giản hơn.

Dựa trên ý tưởng này, ta có thể duyệt qua tất cả các cách có thể chọn $a_i$ ~a_i~ và giải bài toán còn lại. Tuy nhiên, trước tiên ta sắp xếp mảng để có thể giải bài toán tìm hai giá trị có tổng bằng một giá trị cho trước trong $O(n)$ ~O(n)~ bằng kỹ thuật hai con trỏ (two pointers).

Do đó, thuật toán thu được có độ phức tạp $O(n^2)$ ~O(n^2)~.

Hướng giải: Tổng bộ ba

Tổng bộ ba

Bình luận